Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HAOYU WANG:
All reports by Author Haoyu Wang:

TR26-187 | 17th September 2026
Yimeng Wang, Haoyu Wang, Pei Wu

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

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) ... more >>>




ISSN 1433-8092 | Imprint