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