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.