比利时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
****************************