Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

RSS-Feed




Revision #1
Authors: Anup Rao, Amir Yehudayoff
Accepted on: 30th August 2014 20:24
Downloads: 1338
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
Downloads: 3220
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.



ISSN 1433-8092 | Imprint