Computer Science/Discrete Mathematics Seminar II

While this talk is a continuation of the one I gave on Tue Nov 25, it will be planned as an independent one. I will not assume knowledge from that talk, and will reintroduce that is needed. (That first lecture gave plenty of background material, and anyone interested can watch it on https://www.ias.edu/video/csdm/2014/1125-AviWigderson).

This talk will describe some of the mathematical techniques that are needed for proving that sum-of-squares algorithms require many rounds to find planted cliques in random graphs. In particular, I will explain how to construct a "dual certificate" (aka vector solution, aka pseudo-expectation) for *every* graph. Using this reduces the problem to showing that a certain random matrix associated to the graph is PSD (Positive Semi-Definite). Proving this statement splits into two sub-problems. One is proving that the expectation of the random matrix is PSD - this part uses the theory of association schemes and in particular the Johnson scheme, which I will introduce. The second is proving that the random matrix is concentrated about its expectation. This will require new large deviation results for matrices with correlated entries. Joint work with Raghu Meka and Aaron Potechin.