## Almost optimal sum of squares lower bound for planted clique

Pravesh Kothari

University of Texas, Austin

March 7, 2016

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.