Lower Bounds for Clique vs. Independent Set

Abstract

We prove an ω(log n) lower bound on the Conon deterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies super polynomial lower bounds for the Alon - Saks - Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity separation for the decision tree analogue of the UP vs. coNP question - namely, unambiguous DNF width vs. CNF width - and then "lift" this separation over to communication complexity using a result from prior work.