Lower Bounds for Clique vs. Independent Set
Mika Göös · 2015
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.