Computer Science & Discrete Mathematics (CSDM)

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.

Locally Decodable Codes (LDCs) are a special type of error correcting codes which are constructed from finite point sets that support many small linear dependencies (e.g. many collinear triples). Despite their importance, there are still huge gaps between the known LDC constructions and lower bounds. In 2008 , Efremenko showed a framework for constructing LDCs from representations of finite groups. We strengthen Efremenko's reduction and use this strengthening, together with known bounds on LDCs, to derive new results on representations. In particular we show that if rho is an n-dimensional irreducible representation of G and rho(g) is not the identity, then it must be n/log|G| far from the identity in rank metric (this bound is the best possible in general).