Tata Institute of Fundamental Research
Randomized Communication Complexity of Set Disjointness
Student Seminar
Speaker:
Sagnik Mukhopadhyay
Organiser:
Kshitij Gajjar
Date:
Friday, 30 Aug 2013, 16:00 to 17:30
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Sagnik Mukhopadhyay |
| Organiser: | Kshitij Gajjar |
| Date: | Friday, 30 Aug 2013, 16:00 to 17:30 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
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.