Theory of Computing ------------------- Title : Separation of Unbounded-Error Models in Multi-Party Communication Complexity Authors : Arkadev Chattopadhyay and Nikhil S. Mande Volume : 14 Number : 21 Pages : 1-23 URL : https://theoryofcomputing.org/articles/v014a021 Abstract -------- 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, Hastad, 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 $\THR$ and $\MAJ$ denote the classes of linear threshold functions that have unbounded weights and polynomially bounded weights, respectively. Further, let $\PAR_k$ ($\ANY_k$) denote the class of functions that are parities of $k$ bits (any $k$-junta, respectively). Denote by $\THR \circ \PAR_k$ the class of depth-2 circuits where the top gate computes a linear threshold function, and the bottom gates compute functions in $\PAR_k$. For every $2 \le k \le \delta \log n$, we show that there exists a function computable by a linear-size $\THR \circ \PAR_k$ circuit, but requires $\exp(n^{\Omega(1)})$-size circuits in the class $\MAJ \circ \SYM \circ \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 $\MAJ \circ \THR \circ \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 \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.