Received: July 2, 2007
Published: October 15, 2007
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.
Licensed under a Creative Commons License