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 belowSpeakers
Affiliation
University of Toronto; Visiting Professor, School of Mathematics