Toniann Pitassi: Lifting with Sunflowers

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.