Lunch In Theory This Thursday (12:00 PM, 03/12, GCS 302c)
Devansh Gupta
Title: Lifting Theorems for One-Way Numbers-on-Forehead Communication
Proving strong lower bounds in one-way NOF communication remains highly challenging in complexity theory. Strong deterministic one-way NOF lower bounds will imply circuit lower bounds, lower bounds for well-known problems in additive combinatorics, and wide applications. Given the important implications of one-way NOF communication lower bounds, developing new techniques for proving strong one-way NOF lower bounds has become a central research direction in computational complexity. However, even fundamental questions in one-way NOF communication remain poorly understood.
In this talk, we introduce the first lifting framework connecting two-party communication to the Numbers-on-Forehead (NOF) model. This framework solves two basic open problems in one-way NOF communication :
Deterministic vs. Randomized Separation: We establish an explicit $\Omega(n/2^k)$ vs. $O(1)$ separation for $k$-party one-way NOF communication. This significantly improves upon the recent square-root separation for only three players (Kelley & Lyu, FOCS 2025).
Quantum vs. Randomized Separation: By lifting the Hidden Matching problem, we provide the first exponential separation between quantum and randomized one-way NOF communication ($O(\log n)$ vs. $\Omega(n^{1/3}/2^{k/3})$). This resolves an open problem proposed by Gavinsky and Pudlák (CCC 2008).