TR11-145 Authors: Alexander A. Sherstov

Publication: 2nd November 2011 21:42

Downloads: 8792

Keywords:

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.