Untitled research work

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.