  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.
