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. For three players, our construction improves the strongest previously known explicit separation, due to Kelley and Lyu (FOCS 2025) building on Kelley, Lovett, and Meka (STOC 2024), from constant randomized versus $\Omega(n^{1/2})$ nondeterministic communication to the optimal constant versus linear separation. Our construction uses algebraic geometry codes to preserve the nondeterministic hardness of generalized inner product while enabling a randomized protocol with constant communication.

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. For three players, our construction improves the strongest previously known explicit separation, due to Kelley and Lyu (FOCS 2025) building on Kelley, Lovett, and Meka (STOC 2024), from constant randomized versus $\Omega(n^{1/2})$ nondeterministic communication to the optimal constant versus linear separation. Our construction uses algebraic geometry codes to preserve the nondeterministic hardness of generalized inner product while enabling a randomized protocol with constant communication.

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.