Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique

Understand

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.