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 n^{1/2 - o(1)} bound on the value of this program for any degree d = o(\log n). Moreover we introduce a new framework that we call \emph{pseudo-calibration} to construct Sum of Squares lower bounds.
This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.