Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Number-On-Forehead:
TR14-060 | 21st April 2014
Anup Rao, Amir Yehudayoff

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revisions: 1

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.

more >>>

ISSN 1433-8092 | Imprint