## Sum-of-squares lower bounds for the planted clique problem

Avi Wigderson

Herbert H. Maass Professor, School of Mathematics

November 25, 2014

Finding large cliques in random graphs and the closely related "planted" clique variant, where a clique of size \(k\) is planted in a random \(G(n,1/2)\) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for \(k = \Theta(\sqrt{n})\). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy.