Lifting Lower Bounds, Communication, and Proofs

Seminar | October 30 | 2-3 p.m. | 310 Sutardja Dai Hall

 Toniann Pitassi, Professor, Department of Computer Science and Department of Mathematics, University of Toronto and Institute for Advanced Study

 Electrical Engineering and Computer Sciences (EECS)

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. Finally, I will sketch a proof of a unified lifting theorem and discuss some new applications.

Toniann Pitassi received a bachelors and masters degrees from Pennsylvania State University and her PhD from the University of Toronto. After that she spent two years as a postdoc at UCSD, followed by faculty positions at the University of Arizona (Computer Science) and the University of Pittsburgh (Mathematics with a joint appointment in Computer Science). Pitassi is currently a Professor of Computer Science at the University of Toronto where she is the Canada Bell Chair in Information Systems. She is also a Member of the Vector Institute in Artificial Intelligence where she is the Principal Investigator for Technology and Society, and holds a five-year Visiting Professor position at the Institute for Advanced Study. Pitassi's primary research interests are computational complexity, data privacy, and fairness in machine learning.