18th Annual IEEE Conference on Computational Complexity (CCC'03)
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness
Aarhus, Denmark
July 07-July 10
ISBN: 0-7695-1879-6
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