School of Technology and Computer Science Seminars

Randomized Communication Complexity of Set Disjointness

by Mr. Sagnik Mukhopadhyay (School of Technology and Computer Science, TIFR)

Friday, August 30, 2013 from to (Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description
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.