Paul received his B.Sc. in Mathematics in 1981, an M.Sc. in Computer Science in 1982, and Ph.D. in Computer Science in 1987, all from the University of Toronto. He was a Post-doctoral Research Associate at M.I.T. for the 1986-87 academic year and joined the University of Washington in 1987.
Paul’s research is in pure and applied computational complexity. A major focus of his research is in proving lower bounds on the resources needed for solving computational problems. Such topics include communication complexity, time-space tradeoff lower bounds, circuit complexity, proof complexity, and data structures, as well as limitations of space-bounded quantum computers. Another focus of his research is on problems related to formal reasoning, including SAT-solving. His research includes applications of computational complexity in formal verification of software and hardware (such as verifying non-linear arithmetic), in the study of databases, and in AI, particularly in knowledge representation, learning, and probabilistic inference.