Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-060 | 30th August 2014 20:24

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revision #1
Authors: Anup Rao, Amir Yehudayoff
Accepted on: 30th August 2014 20:24
Keywords:

Abstract:

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof
showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

Changes to previous version:

In this version we add a proof of Sherstov's discrepancy bound, so that the deterministic lower bound is fully explained. We also made some minor edits to references.

Paper:

TR14-060 | 21st April 2014 08:34

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

TR14-060
Authors: Anup Rao, Amir Yehudayoff
Publication: 21st April 2014 08:34
We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof
showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.