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.