Abstract

I will describe a new polynomial time algorithm for the planted clique problem in the semirandom model introduced by Feige and Kilian in 1999. Our algorithm succeeds for k approaching the ~\sqrt{n} threshold at which the best-known polynomial time algorithms solve the average-case planted clique problem. This nearly resolves an open question of Feige. Specifically, in the Feige-Kilian model, a graph on n vertices is generated by choosing a k-clique on vertex set S, and 1.\emph{random choice:} including each edge in cut(S) independently with probability p, 2. \emph{worst-case choice:} choosing the rest of the edges arbitrarily and adversarially and 3. \emph{monotone adversary:} deleting any arbitrary subset of edges in cut(S). For any \epsilon>0, our algorithm runs in time n^{O(1/\epsilon)}-time and recovers a k-clique in the semirandom model whenever k \geq O(n^{0.5+\epsilon}) (for p=1/2). Prior to our work, the best known polynomial-time algorithm (due to Mckenzie, Mehta and Trevisan, and Charikar, Steinhardt and Valiant) needed k \geq O(n^{2/3}). Our algorithms extend to arbitrary p and improve on the prior best guarantee whenever p \leq 1-n^{-\delta} for small enough \delta>0. In contrast to the average-case planted clique problem, where natural spectral methods or semidefinite programming achieve the best-known guarantees, our algorithm relies crucially on high constant-degree sum-of-squares relaxation of the k-clique integer program. Our analysis of this relaxation relies on a new conceptual connection between semirandom planted clique and refuting biclique numbers in \emph{imbalanced} random bipartite graphs. Seen from this vantage point, prior works implicitly use spectral or semidefinite refutations that appear to run into a barrier at k\sim n^{2/3}. We depart from spectral certificates and instead give a refutation that succeeds for k approaching n^{0.5} by relying on a simple geometric property of vectors in \ell_2. We also provide some evidence that improving our refutations for imbalanced bicliques needs new techniques by proving a lower bound in the low-degree polynomial model.