Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-145 | 2nd November 2011 20:33

The Multiparty Communication Complexity of Set Disjointness



We study the set disjointness problem in the number-on-the-forehead model.

(i) We prove that $k$-party set disjointness has randomized and nondeterministic
communication complexity $\Omega(n/4^k)^{1/4}$ and Merlin-Arthur complexity $\Omega(n/4^k)^{1/8}.$
These bounds are close to tight. Previous lower bounds (2007-2008) for $k\geq3$ parties
were weaker than $n^{1/(k+1)}/2^{k^2}$ in all three models.

(ii) We prove that solving $\ell$ instances of set disjointness requires $\ell\cdot\Omega(n/4^k)^{1/4}$
bits of communication, even to achieve correctness probability exponentially close to
$1/2.$ This gives the first direct-product result for multiparty set disjointness, solving an
open problem due to Beame, Pitassi, Segerlind, and Wigderson (2005).

(iii) We construct a read-once $\{\wedge,\vee\}$-circuit of depth $3$ with exponentially small
discrepancy for up to $k\approx\frac12\log n$ parties. This result is optimal with respect to depth
and solves an open problem due to Beame and Huynh-Ngoc (FOCS '09), who gave a
depth-$6$ construction. Applications to circuit complexity are given.

The proof technique of this paper departs significantly from previous work and is
of independent interest.

ISSN 1433-8092 | Imprint