loading...
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness
Aarhus, Denmark July 07-July 10
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.121441418th Annual IEEE Conference on Comput ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Xiaodong Sun, Institute for Advanced Study
Subhash Khot, Princeton University
Xiaodong Sun, Institute for Advanced Study
We study the communication complexity of the set disjointness problem in the general multi-party model. For t players, each holding a subset of a universe of size n, we establish a near-optimal lower bound of \Omega (n=(t log t)) on the communication complexity of the problem of determining whether their sets are disjoint. In the more restrictive one-way communication model, in which the players are required to speak in a predetermined order, we improve our bound to an optimal \Omega (n/t). These results improve upon the earlier bounds of \Omega (n/t2) in the general model, and \Omega \left( {E^2 n/t^{1 + E} } \right) in the one-way model, due to Bar-Yossef, Jayram, Kumar, and Sivakumar [5]. As in the case of earlier results, our bounds apply to the unique intersection promise problem.
Citation:
Amit Chakrabarti, Subhash Khot, Xiaodong Sun, Subhash Khot, Xiaodong Sun, "Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness," ccc, pp.107, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.