We construct a simple function that has small unbounded-error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with subexponential advantage over random guessing has cost essentially $\Omega(\sqrt{n}\,/\,4^k)$ bits. This separates these classes up to $k \leq \delta\log n$ players for any constant $\delta < 1/4$, and gives the largest known separation by an explicit function in this regime of $k$. Our analysis is elementary and self-contained, inspired by the methods of Goldmann, Håstad, and Razborov (Computational Complexity, 1992). After initial publication of our work as a preprint (ECCC, 2016), Sherstov pointed out to us that an alternative proof of an $\Omega((n\,/\,4^k)^{1/7})$ separation is implicit in his prior work (SICOMP, 2016). Furthermore, based on his prior work (SICOMP, 2013 and SICOMP, 2016), Sherstov gave an alternative proof of our constructive $\Omega(\sqrt{n}\,/\,4^k)$ separation and also produced a stronger non-constructive $\Omega(n\,/\,4^k)$ separation. These results are explained in Sherstov's preprint (ECCC, 2016) and in article 14/22 in Theory of Computing.

Our result has the following consequence for boolean threshold circuits. Let $\text{THR}$ and $\text{MAJ}$ denote the classes of linear threshold functions that have unbounded weights and polynomially bounded weights, respectively. Further, let $\text{PAR}_k$ ($\text{ANY}_k$) denote the class of functions that are parities of $k$ bits (any $k$-junta, respectively). Denote by $\text{THR} \circ \text{PAR}_k$ the class of depth-2 circuits where the top gate computes a linear threshold function, and the bottom gates compute functions in $\text{PAR}_k$. For every $2 \le k \le \delta \log n$, we show that there exists a function computable by a linear-size $\text{THR} \circ \text{PAR}_k$ circuit, but requires $\exp\left({n^{\Omega(1)}}\right)$-size circuits in the class $\text{MAJ} \circ \text{SYM} \circ \text{ANY}_{k-1}$, where the gates in the middle layer compute symmetric functions. Applying a result of Goldmann et al. (loc. cit.) to the above, similar lower bounds on the size of circuits of the form $\text{MAJ} \circ \text{THR} \circ \text{ANY}_{k-1}$ for computing the function follow.

The main technical ingredient of our proof is to exhibit a composed function of the form $f \circ \text{XOR}$ which has exponentially small discrepancy while $f$ has sign-degree just 1. An interesting aspect of our composed function is that the block size of the inner XOR function is fixed to 1, independent of $k$, the number of players.

A preliminary version of this paper appeared as ECCC technical report TR 16-095.