We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits.
This yields the strongest known explicit separation up to $k \leq \delta\log n$ players, where $\delta < 1$ is a constant. After an initial manuscript of our work was published, Sherstov pointed out to us that such a strong separation can also be obtained by a careful combination of implicit and explicit results from previous works. The analysis done in our work, inspired from the work of Goldmann et al. ['92], is more elementary and direct. The alternate route of combining results and ideas of much more recent work requires the use of approximation theory and other tools.
This has the following consequence for boolean Threshold circuits: let $\text{THR}$ and $\text{MAJ}$ denote respectively the classes of linear threshold functions that have unbounded weights and polynomially bounded weights. Further, let $\text{PAR}_k$ ($\text{ANY}_k$) denote the class of functions that are parities of $k$ bits (any $k$-junta). For every $2 \le k \le \delta \log n$, we show that there exists a function in linear size $\text{THR} \circ \text{PAR}_k$ that needs $2^{n^{\Omega(1)}}$ size to be computed by every circuit in the class $\text{MAJ} \circ \text{SYM} \circ \text{ANY}_{k-1}$, where $\text{SYM}$ represents the class of all symmetric functions. Applying a result of Goldmann et al. ['92] 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 result is to show that a composed function of the form $f \circ \text{PAR}$ has exponentially small discrepancy while $f$ has sign degree just 1. An interesting aspect of our work is that the block size of the inner $\text{XOR}$ function is fixed to 1, independent of the number of players $k$.
We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits. Such a separation was first shown for $k=2$ independently by Buhrman et al. ['07] and Sherstov ['08]. A very recent work of Sherstov ['14] can be combined with an earlier work of Beigel ['94] to yield such a separation for up to $k = \Theta(\log\log n)$ players. To the best of our knowledge, our result provides the first such separation that works all the way up to $k \leq \delta \log n$ players, where $\delta < 1$ is a constant. Additionally, our communication lower bounds for $k$-party probabilistic protocols for a function that has efficient unbounded error protocols are quantitatively stronger than previous bounds. In particular, for any constant $k$, our bound on communication for such a function is $\Omega\big(n^{1/2}\big)$ in contrast to the best known previous bound of $\Omega\big(n^{1/3}\big)$.
This has the following consequence for boolean Threshold circuits: let $\text{THR}$ and $\text{MAJ}$ denote respectively the classes of linear threshold functions that have unbounded weights and polynomially bounded weights. Further, let $\text{PAR}_k$ ($\text{ANY}_k$) denote the class of functions that are parities of $k$ bits (any $k$-junta). For every $2 \le k \le \delta \log n$, we show that there exists a function in linear size $\text{THR} \circ \text{PAR}_k$ that needs $2^{n^{\Omega(1)}}$ size to be computed by every circuit in the class $\text{MAJ} \circ \text{SYM} \circ \text{ANY}_{k-1}$, where $\text{SYM}$ represents the class of all symmetric functions. Applying a result of Goldmann et al. ['92] 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 result is to show that a composed function of the form $f \circ \text{PAR}$ has exponentially small discrepancy while $f$ has sign degree just 1.
We thank Sasha Sherstov for pointing out the following to us.
1) A separation between PP and UPP was already implicit from [26, 27] even for upto $\Theta(\log(n))$ players.
2) An explicit function in UPP requiring $\Omega(\sqrt{n})$ PP cost is also implicit from a previous work.
We will make the necessary changes to this manuscript to correctly account for previous work and how it relates to ours, and update it soon.
