In this talk we will 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 sufïcient, regardless of $n$. In the model of private random coins $O(k +\ log \log n)$ bits sufïce. Both results are asymptotically tight.
