We prove that with high probability over the choice of a random graph G from the Erd\H{o}s-R\'enyi distribution G(n,1/2), the n^{O(d)}-time degree d Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least n^{1/2-c(d/\log n)^{1/2}} for some constant c>0.
This yields a nearly tight ... more >>>

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>>