Talks
Fall 2021

Sum-Of-Squares Lower Bound for Statistical Problems
Wednesday, November 10th, 2021, 10:00 am–11:00 am
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.
Attachment | Size |
---|---|
![]() | 6.01 MB |