Computer Science/Discrete Mathematics Seminar I | |

Topic: | Lower bounds for clique vs. independent set |

Speaker: | Mika Göös |

Affiliation: | University of Toronto |

Date: | Monday, February 23 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | http://video.ias.edu/csdm/2015/0223-MikaGoos |

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.