ECCC-Report TR14-060https://eccc.weizmann.ac.il/report/2014/060Comments and Revisions published for TR14-060en-usSat, 30 Aug 2014 20:24:38 +0300
Revision 1
| Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness |
Anup Rao,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2014/060#revision1We 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.Sat, 30 Aug 2014 20:24:38 +0300https://eccc.weizmann.ac.il/report/2014/060#revision1
Paper TR14-060
| Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness |
Anup Rao,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2014/060We 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.Mon, 21 Apr 2014 08:34:18 +0300https://eccc.weizmann.ac.il/report/2014/060