Back to Videos

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 .


Download Abstract