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 : http://www.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.