##### 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

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