LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
A More Efficient Sifting Lemma and a Stronger 3-Player Communication Lower Bound
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

A More Efficient Sifting Lemma and a Stronger 3-Player Communication Lower Bound

121 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Zander Kelley, speaking in the Institute for Advanced Study's Computer Science/Discrete Mathematics seminar, presents joint work with Xin Lyu on multiparty communication complexity. The talk builds on his earlier result with Lovett and Meka, which separated randomized from deterministic three-player protocols in the number-on-forehead model by proving a deterministic lower bound of Omega(n^{1/3}) for an explicit function. Kelley explains the sifting lemma at the heart of that proof, a tool showing that any bipartite graph with large grid norm must contain a smaller, denser induced subgraph, and introduces a more efficient version of it. The sharper lemma improves the lower bound to Omega(n^{1/2}). He walks through the new structural claim that small cylinder intersections can be covered by a handful of compact slice functions, and compares the technique to Szemeredi's Triangle Removal Lemma, which performs an analogous covering job for ordinary graphs. The talk is technical and aimed at a complexity theory audience.

At a glance

Lecture facts

Runtime compared with the other 148 Computer Science lectures
Runtime2 h 1 m
Compared with Computer ScienceLonger than 93%
Source channelInstitute for Advanced Study (YouTube)