Fall 2018

BPP Lifting and Its Applications

Tuesday, September 11th, 2018 2:30 pm3:30 pm

Add to Calendar


Toni Pitassi (University of Toronto)

Hardness escalation or query-to-communication lifting is a method of proving tight upper and lower bounds on the communication complexity of a composed function or relation by a reduction to the query complexity of the base function. This talk will primarily be a tutorial. I will first discuss the many applications of lifting, including new and improved lower bounds for monotone complexity, game theory, proof complexity and extended formulations. Secondly, I will sketch the main ideas in the proof of the BPP lifting theorem (joint work with Mika Göös and Thomas Watson).