CS 2429- Foundations of Communication Complexity Lecture #6: Fall, 2012 CS 2429- Foundations of Communication Complexity

The Clique vs. Independent Set (CIS) is a problem in two-player communication complexity. The CIS game is played on an undirected n vertex graph G = (V,E) that is known to both the players Alice and Bob. As input, Alice gets a set C ⊆ V that spans a clique in G while Bob holds an independent set I ⊆ V. The objective is to decide whether C ∩ I = ∅, i.e., compute the value CISG(C, I): = |C ∩ I|. Thus, the CIS problem is a highly structured special case of the disjointness problem; for example, we always have that CISG(C, I) ∈ {0, 1}. Interestingly, for many graphs G the deterministic communication complexity D(CISG) is not well-understood; in this note we explain why the CIS problem is important and survey some of the known results.