ECCC-Report TR11-145https://eccc.weizmann.ac.il/report/2011/145Comments and Revisions published for TR11-145en-usWed, 02 Nov 2011 21:42:29 +0200
Paper TR11-145
| The Multiparty Communication Complexity of Set Disjointness |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2011/145We 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.Wed, 02 Nov 2011 21:42:29 +0200https://eccc.weizmann.ac.il/report/2011/145