Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Department Colloquium

Toniann Pitassi

University of Toronto and Institute for Advanced Study

A Survey of Recent Progress in Lower Bounds via Lifting

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.

Host: Sam Buss

April 15, 2019

11:00 AM

AP&M 6402

****************************