Sum-of-squares Lower Bounds for Planted Clique

Abstract

Finding 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 = Θ(√n). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy. We prove the first average case lower bound for this model: for almost all graphs in G(n,1/2), r rounds of the SOS hierarchy cannot find a planted k-clique unless k ≥ (√n/log n)1/rCr. Thus, for any constant number of rounds planted cliques of size no(1) cannot be found by this powerful class of algorithms. This is shown via an integrability gap for the natural formulation of maximum clique problem on random graphs for SOS and Lasserre hierarchies, which in turn follow from degree lower bounds for the Positivestellensatz proof system.