Loading...
Please wait, while we are loading the content...
Similar Documents
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness (2014)
| Content Provider | CiteSeerX |
|---|---|
| Author | Rao, Anup Yehudayoff, Amir |
| Abstract | We show that the deterministic number-on-forehead communication complexity of set dis-jointness for k parties on a universe of size n is Ω(n/4k). This gives the first lower bound that is linear in n, nearly matching Grolmusz’s upper bound of O(log2(n) + k2n/2k). We also sim-plify Sherstov’s proof showing an Ω( n/(k2k)) lower bound for the randomized communication complexity of set disjointness. 1 |
| File Format | |
| Publisher Date | 2014-01-01 |
| Access Restriction | Open |
| Subject Keyword | Multiparty Communication Complexity Simplified Lower Bound Set Disjointness Randomized Communication Complexity Deterministic Number-on-forehead Communication Complexity Sherstov Proof Grolmusz Upper Bound |
| Content Type | Text |