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

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. 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 \geq n^{1/2r}/2^{r}\). Thus, for any constant number of rounds, planted cliques of size \(n^{o(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. I plan to explain these proof systems and the typical steps in proving lower bounds for them, which we will follow in this proof. First, we introduce a natural "vector-solution" (or "dual certificate") for the given system of polynomial equations representing the problem for every fixed input graph. Then we show that the associated matrix to this solution is PSD (positive semi-definite) with high probability over the choice of the input graph. This requires the use of certain tools. One is the theory of association schemes, and in particular the eigenspaces and eigenvalues of the Johnson scheme. Another is a combinatorial method we develop to compute (via traces) norm bounds for certain random matrices whose entries are highly dependent. No special background will be assumed. Joint work with Raghu Meka and Aaron Potechin