Computer Science/Discrete Mathematics Seminar II

Simplified Lifting Theorems in Communication Complexity via Sunflowers

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 .

Date & Time

October 06, 2020 | 10:30am – 12:30pm

Location

Simonyi Hall 101 and Remote Access - see Zoom link below

Affiliation

University of Toronto; Visiting Professor, School of Mathematics