Theory of Computing
-------------------
Title : The Randomized Communication Complexity of Set Disjointness
Authors : Johan Haastad and Avi Wigderson
Volume : 3
Number : 11
Pages : 211-219
URL : https://theoryofcomputing.org/articles/v003a011
Abstract
--------
We study the communication complexity of the disjointness function,
in which each of two players holds a k-subset of a universe of
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.