![Real Analysis in Computer Science_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Real%20Analysis%20in%20Computer%20Science_hi-res.jpg?h=e2b42a27&itok=jpgiJZrK)
Abstract
Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k 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 k ~ sqrt(n). Here we show that beating sqrt(n) would require substantially new algorithmic ideas, by proving an integrality gap for the problem in the Lasserre/Sum of Squares hierarchy, the most powerful class of semi-definite programming algorithms we know of. Our (average case) lower bound uses tools from the classical theory of association schemes and some new large deviation bounds for matrix-valued polynomials which could be of independent interest.
This is joint work with Avi Wigderson.