REPORTS > DETAIL:

### Paper:

TR15-012 | 24th January 2015 19:26

#### Lower Bounds for Clique vs. Independent Set

TR15-012
Authors: Mika Göös
Publication: 25th January 2015 12:53
Downloads: 2495
Keywords:

Abstract:

We prove an $\omega(\log n)$ lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial 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.

ISSN 1433-8092 | Imprint