Sum-of-squares lower bounds for planted clique

Understand

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 ~ sqrt(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^{1/2r} (up to logarithmic factors).