Revised: March 24, 2017

Published: December 28, 2018

**Keywords:**complexity theory, communication complexity, weakly unbounded error, unbounded error, NOF model

**Categories:**complexity theory, lower bounds, communication complexity, multiparty communication complexity, NOF model, complexity classes, separation of complexity classes

**ACM Classification:**F.1.3, F.2.3

**AMS Classification:**68Q17, 68Q15

**Abstract:**
[Plain Text Version]

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.