
Revised: March 24, 2017
Published: December 28, 2018
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 Ω(√n/4k) bits. This separates these classes up to k≤δlogn players for any constant δ<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 Ω((n/4k)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 Ω(√n/4k) separation and also produced a stronger non-constructive Ω(n/4k) 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 PARk (ANYk) denote the class of functions that are parities of k bits (any k-junta, respectively). Denote by THR∘PARk the class of depth-2 circuits where the top gate computes a linear threshold function, and the bottom gates compute functions in PARk. For every 2≤k≤δlogn, we show that there exists a function computable by a linear-size THR∘PARk circuit, but requires exp(nΩ(1))-size circuits in the class MAJ∘SYM∘ANYk−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∘THR∘ANYk−1 for computing the function follow.
The main technical ingredient of our proof is to exhibit a composed function of the form f∘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.