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

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.