Paul Beame

Paul Beame is a Professor and Associate Director for Facilities at the Paul G. Allen School of Computer Science & Engineering (University of Washington). He earned his B.Sc. in Mathematics (1981), M.Sc. in Computer Science (1982), and Ph.D. in Computer Science (1987) from the University of Toronto, followed by postdoctoral work at MIT (1986-87). His research spans computational complexity, proof complexity, quantum computing, and formal verification, with applications to databases and AI.

• Research Interests: Computational complexity theory, proof complexity, SAT-solving, quantum algorithms, time-space tradeoffs, communication complexity, circuit complexity, knowledge representation, probabilistic inference.
• Recent Publications: Focus on quantum time-space tradeoffs, multiparty communication complexity, formal verification of nonlinear arithmetic, and lower bounds for circuit and proof systems. Articles appear in ACM Transactions on Computation Theory, SIAM Journal on Computing, and conferences like STOC, FOCS, and NeurIPS.
• Teaching & Service: Active in theoretical computer science education and professional service, including program committee roles and tutorials.
• Personal: Engages in sports like squash and softball.