Demo Section: Dynamic Block

We construct very efficient argument systems for proving the correctness of bounded-space computations, based on the existence of one-way functions. Our argument system applies to general computations running in time T and space S. The communication and verification time are poly-logarithmic in T and linear in S. The honest prover's running time is polynomial in T, so the protocol is doubly-efficient. All complexities are polynomial in the security parameter of the one-way function, and verification is also linear in the input length.

Prior to this work, doubly-efficient argument systems with poly-logarithmic dependence on T required assuming (at least) the existence of collision-resistant hash functions [Kilian, STOC 1992]. For unconditionally sound doubly-efficient protocols, the RRR protocol for bounded-space computations [Reingold, Rothblum and Rothblum, STOC 2016] has communication and verification complexities that grow with an arbitrarily small constant power of T.

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.