Computer Science Distinguished Lecture Series
Toniann Pitassi
Abstract:
Ever since Yao introduced the communication complexity model in 1979, it has played a pivotal role in our understanding of limitations for a wide variety of problems in Computer Science. In this talk, I will present the lifting method, whereby communication lower bounds are obtained by lifting much simpler lower bounds. I will show how lifting theorems have been used to solve many open problems in a variety of areas of computer science, including: circuit complexity, proof complexity, combinatorial optimization (size of linear programming formulations), cryptography (linear secret sharing schemes), game theory and privacy. Time permitting, I will sketch a proof of a unified lifting theorem and discuss some new applications to pseudodeterminism.
Biography:
Toniann Pitassi received a bachelors and masters degrees from Pennsylvania State University and then a PhD from the University of Toronto in 1992. After that, she spent two years as a postdoc at UCSD, and began teaching at the University of Pittsburgh, then at the University of Arizona. In the fall of 2001, Pitassi moved back to Toronto, where she is currently a professor in the Computer Science Department, with a joint appointment in Mathematics.
