Randomized Communication Complexity of Set Disjointness



Friday, 30 August 2013, 16:00 to 17:30


  • D-405 (D-Block Seminar Room)


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.