Volume 3 (2007)
Article 11 pp. 211-219
The Randomized Communication Complexity of Set Disjointness
Received: July 2, 2007
Published: October 15, 2007
Published: October 15, 2007
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.