2 h 1 min
Seminar
A More Efficient Sifting Lemma and a Stronger 3-Player Communication Lower Bound
Institute for Advanced Study
Recording
Abstract
Zander Kelley presents joint work with Xin Lyu separating randomized and deterministic three-player communication in the number-on-forehead model. Earlier work by Kelley, Lovett and Meka gave an explicit function with an efficient randomized protocol but a deterministic lower bound of Ω(n^(1/3)). The argument studies whether its yes-instances can be covered efficiently by small cylinder intersections. A sifting lemma finds a denser induced subgraph inside a bipartite graph with large grid norm. An improved version raises the communication lower bound to Ω(n^(1/2)). The key structural result covers small cylinder intersections by a few reasonably small slice functions; the talk compares this simplification with Szemerédi’s triangle removal lemma.
Topics
- three-player communication, broader topic: communication
- number-on-forehead model, broader topic: model
- cylinder intersections, search World Wide
- sifting lemma, search World Wide
- induced subgraph, search World Wide
- grid norm, search World Wide
- slice functions, search World Wide
- triangle removal lemma, search World Wide