Talks
Fall 2021

Sum-Of-Squares Lower Bound for Statistical Problems

Wednesday, November 10th, 2021, 10:00 am11:00 am

Add to Calendar

Speaker: 

Samuel Hopkins (UC Berkeley)

Location: 

Calvin Lab Auditorium

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.

AttachmentSize
PDF icon Slides6.01 MB