printable pdf
比利时vs摩洛哥足彩 ,
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

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