Talks
Fall 2021

Sum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds

Monday, September 13th, 2021, 10:20 am10:45 am

Add to Calendar

Speaker: 

Aaron Potechin (University of Chicago)

Location: 

Calvin Lab Auditorium

The sum of squares hierarchy is a powerful method for solving statistical inference problems and sum of squares lower bounds give compelling evidence that these problems are hard. However, analyzing the sum of squares hierarchy can be quite challenging. In recent years, low-degree polynomials have been studied as an alternative method for analyzing statistical inference problems which is simpler yet still extremely effective. In this talk, I will describe how sum of squares lower bounds and low-degree polynomial lower bounds are related. I will then compare what is known about sum of squares lower bounds to what is known about low-degree polynomial lower bounds.

AttachmentSize
PDF icon Slides326.57 KB