School of Technology and Computer Science Seminars
Clique vs Independent Set Game: A Tight Bound
by Mr. Sagnik Mukhopadhyay (School of Technology and Computer Science, TIFR)
Friday, May 15, 2015
from
to
(Asia/Kolkata)
at A-212 (STCS Seminar Room)
at A-212 (STCS Seminar Room)
Description |
The clique vs independent set game (CIS(G)) on a graph $G$ is a game between two parties - Alice and Bob. Alice get s a set of vertices, $C$, which forms a clique in $G$ and Bob gets a set of vertices, $I$, which forms an independent set in $G$. Clearly, $C$ and $I$ can intersect in only 1 vertex. The question the players try to answer is whether $C \cap I = \emptyset$ or not. By a result of Yannakakis, we know that this problem can be solved deterministically by communicating $O(\log^2 n)$ bits where $n$ is the size of vertex set in $V$. It has been an open problem for a long time whether this upper bound can be improved. A recent result of Goos, Pitassi and Watson shows that this upper bound is tight, i.e., there is a graph for which the CIS game requires $\tilde{\Omega}(\log^2 n)$ communication. In the talk, we will see proof-sketches of these results. |