SCS Special Seminar

Wednesday, February 27, 2019 - 2:00pm to 4:00pm


ASA Conference Room 6115 Gates Hillman Centers


TONIANN PITASSI, Professor and Bell Canada Chair in Information Systems

A Survey of Recent Progress in Lower Bounds via Lifting

Speaker: Toniann Pitassi

Location: GHC 6115

A Survey of Recent Progress in Lower Bounds via Lifting

Ever since Yao introduced the communication complexity 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 what makes them exciting/useful, but also difficult to prove. Finally, I will highlight how these lifting theorems have been used to solve several open problems in circuit complexity, proof complexity, combinatorial optimization (size of linear programming formulations), and cryptography (linear secret sharing schemes).

Faculty Host: Venkatesan Guruswami


For More Information, Contact:


Special Seminar