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...
Read More