Almost optimal sum of squares lower bound for planted clique

Finding cliques in random graphs and the related planted variant where one wants to recover an added clique of size $k$ added to a random $G(n, 1/2)$ graph, have been extensively studied questions in algorithm design. Despite intense effort, state of the art polynomial time algorithms can find added cliques to random graphs only when $k \gg \sqrt{n}$.This has led to the conjectured hardness of the problem for $k \ll \sqrt{n}$ with many interesting applications. Recent works (Meka, Potechin and Wigderson 2015, Deshpande and Montanari 2015) have considered the question of understanding the efficacy of the powerful sum of squares semi-definite programming hierarchy in solving the planted clique problem. However, the question of whether a polynomial time algorithm based on this scheme succeeds in finding planted cliques of size $\ll \sqrt{n}$ remained unresolved. In this work, we settle this question by showing that any polynomial time algorithm from the sum of squares hierarchy fails to detect added cliques of size $\ll \sqrt{n}$. A key part of our proof is a new general construction of a lower bound witness (a.k.a. certificate or "pseudo-expectation") that could yield tight SoS lower bounds for many other average case problems. Joint work with Boaz Barak, Samuel Hopkins, Jon Kelner, Ankur Moitra and Aaron Potechin.



University of Texas, Austin