Volume 3 (2007) Article 11 pp. 211-219
The Randomized Communication Complexity of Set Disjointness
by
Received: July 2, 2007
Published: October 15, 2007
Download article from ToC site:
[PDF (120K)] [PS (209K)] [Source ZIP]
Keywords: communication complexity, randomized protocol, set disjointness
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.