Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-187 | 17th September 2026 09:16

An Explicit Optimal Separation of BPP from NP in Number-on-Forehead Communication Complexity

RSS-Feed




TR26-187
Authors: Yimeng Wang, Haoyu Wang, Pei Wu
Publication: 17th September 2026 14:40
Downloads: 155
Keywords: 


Abstract:

For every fixed $k\ge3$, we construct an explicit total Boolean function in the $k$-player number-on-forehead model with public-coin randomized communication complexity $O_k(1)$ and nondeterministic communication complexity $\Omega_k(n)$, where $n$ is the number of bits on each forehead. This extends the explicit three-player separations of Kelley, Lovett, and Meka (STOC 2024) and Kelley and Lyu (FOCS 2025) to every fixed number of players, and as a side product improves the three-player nondeterministic lower bound from $\Omega(n^{1/2})$ to the optimal $\Omega(n)$. Our construction is based on algebraic geometry codes.



ISSN 1433-8092 | Imprint