Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique

Computer Science/Discrete Mathematics Seminar I
Topic:Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique
Speaker:Raghu Meka
Affiliation:DIMACS (Rutgers); Member, School of Mathematics
Date:Monday, May 13
Time/Room:1:30pm - 3:30pm/S-101
Video Link:https://video.ias.edu/csdm/1213/0513-RaghuMeka

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 a lower bound for the problem in the Lasserre hierarchy, the most powerful class of semi-de finite 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. Joint work with Avi Wigderson