Toniann Pitassi: Lifting with Sunflowers

Tuesday, December 1, 2020 - 4:00pm to 5:30pm
Zoom Registration Link:
Toniann Pitassi, U of Toronto and IAS

Abstract:  In this talk I will first motivate lifting theorems where lower bounds on communication complexity for composed functions are obtained by a general simulation theorem, essentially showing that no protocol can do better than the obvious "query" algorithm. I'll give a self-contained simplified proof of lifting that uses the sunflower lemma, and then give some applications and open problems.

This is joint work with Shachar Lovett, Raghu Meka, Ian Mertz and Jiapeng Zhang.