Abstract

I will give an overview of average-case lower bounds against the powerful SoS hierarchy of convex programs. Time permitting, I will discuss problems such as planted clique, random constraint satisfaction, sparse PCA, optimization of random Hamiltonians, stochastic block models, etc.. I will discuss the main techniques used to prove these lower bounds, in particular the powerful but mysterious pseudocalibration approach. A wealth of open problems remain; I will mention at least a few.

Attachment

Video Recording