Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 14 (2018) Article 21 pp. 1-23
Separation of Unbounded-Error Models in Multi-Party Communication Complexity
Received: September 7, 2016
Revised: March 24, 2017
Published: December 28, 2018
Download article from ToC site:
[PDF (290K)] [PS (1490K)] [Source ZIP]
Keywords: complexity theory, communication complexity, weakly unbounded error, unbounded error, NOF model
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 Ω(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 THRPARk 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 2kδlogn, we show that there exists a function computable by a linear-size THRPARk circuit, but requires exp(nΩ(1))-size circuits in the class MAJSYMANYk1, 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 MAJTHRANYk1 for computing the function follow.

The main technical ingredient of our proof is to exhibit a composed function of the form fXOR 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.