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

A central goal in complexity theory is to prove separations between randomized and deterministic models of computation. In communication complexity, a key challenge is to establish lower bounds for multiparty protocols in the number-on-forehead (NOF) model. Recent work by Kelley, Lovett, and Meka provided a separation for an explicit 3-player function, proving a deterministic lower bound of Ω(n^{1/3}) for a function with an efficient randomized protocol.

The proof of this lower bound involved showing that the ‘yes’ instances of a function cannot be efficiently covered by small "cylinder intersections" -- the basic unit of NOF communication. This analysis hinges on a sifting lemma for bipartite graphs, which guarantees that any graph with a large "grid norm" must contain a smaller, much denser induced subgraph. In this talk, based on joint work with Xin Lyu, I will discuss a new, more efficient version of this sifting lemma. This strengthening of the core technical tool allows us to improve the 3-player lower bound to Ω(n^{1/2}), achieving a stronger separation.

Specifically, we prove a new structural result about small cylinder intersections: that they can be covered by a few reasonably small "slice functions". I will explain how this result can be productively compared with Szemerédi's Triangle Removal Lemma for graphs, which also gives a way to cover small cylinder intersections by something simpler.