Videos

Simplified Lifting Theorems in Communication Complexity via Sunflowers

Presenter
October 6, 2020
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 any better than the obvious "query" algorithm. I'll give a self-contained simplified proof of lifting which uses the sunflower lemma. The simplified proof is joint with Shachar Lovett, Raghu Meka, Ian Mertz, and Jiapeng Zhang .