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

Raghu Meka, Avi Wigderson

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 substantia…