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) )
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. |