  Finding cliques in random graphs and the closely related "planted" clique
variant, where a clique of size t 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 t =
Theta(sqrt(n)). Here we show that beating sqrt(n) would require substantially
new algorithmic ideas, by proving a lower bound for the problem in the
sum-of-squares (or Lasserre) hierarchy, the most powerful class of
semi-definite programming algorithms we know of: r rounds of the sum-of-squares
hierarchy can only solve the planted clique for t > sqrt(n)/(C log n)^(r^2).
Previously, no nontrivial lower bounds were known. Our proof is formulated as a
degree lower bound in the Positivstellensatz algebraic proof system, which is
equivalent to the sum-of-squares hierarchy. The heart of our (average-case)
lower bound is a proof that a certain random matrix derived from the input
graph is (with high probability) positive semidefinite. Two ingredients play an
important role in this proof. The first is the classical theory of association
schemes, applied to the average and variance of that random matrix. The second
is a new large deviation inequality for matrix-valued polynomials. Our new tail
estimate seems to be of independent interest and may find other applications,
as it generalizes both the estimates on real-valued polynomials and on sums of
independent random matrices.
