Toniann Pitassi: A Survey of Recent Progress in Lower Bounds

Abstract: Ever since Yao introduced the communication model in 1979, it has played a pivotal role in our understanding of lower bounds 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 present several lifting theorems that we have obtained and explain what makes the exciting/useful but also difficult to prove. Finally I will highlight how they have been used to solve several open problems in circuit complexity, proof complexity, optimization, cryptography, game theory and privacy.Short Bio: Toniann Pitassi is a professor and Bell Canada Chair in Information Systems at the University of Toronto. She also holds a five-year visiting professorship at the Institute for Advanced Study. She earned her bachelor’s and master’s degrees from Penn State and her PhD from the University of Toronto. She has held previous positions at UC San Diego, University of Pittsburgh, and University of Arizona. Pitassi was an invited speaker at the International Congress of Mathematicians and was recently elected as an ACM fellow. Her primary research is in computational complexity, proof complexity, privacy and fairness.