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       : http://www.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.