Volume 3 (2007) Article 11 pp. 211-219

The Randomized Communication Complexity of Set Disjointness

by Johan Håstad and Avi Wigderson

Received: July 2, 2007
Published: October 15, 2007
DOI: 10.4086/toc.2007.v003a011

Download article from ToC site:
[PS (206K)]    [PS.GZ (60K)]    [PS.ZIP (60K)]
[PDF (114K)]    [DVI (74K)]    [TeX (23K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: communication complexity, randomized protocol, set disjointness
Categories: short, complexity theory, algorithms, communication complexity
ACM Classification: F.2.2
AMS Classification: 68Q25

Abstract: [Plain Text Version]

We study the communication complexity of the disjointness function, in which each of two players holds a k-subset of a universe of size n and the goal is to determine whether the sets are disjoint. In the model of a common random string we prove that O(k) communication bits are sufficient, regardless of n. In the model of private random coins O(k + log log n) bits suffice. Both results are asymptotically tight.