Abstract
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).