Fall 2020

Pedagogical Talk: Failure of Low-Degree Polynomials

Thursday, Sep. 24, 2020 11:15 am12:15 pm PDT

Add to Calendar


Alex Wein, NYU

Low-degree polynomials are a restricted model of computation that captures the best known algorithms for a broad class of problems in high-dimensional statistics. As such, lower bounds against low-degree polynomials are a form of concrete evidence for average-case computational hardness. In this talk, I will give an introduction to some of the techniques used to prove lower bounds against low-degree polynomials for three different types of problems: detection, recovery, and optimization.

PDF icon low-deg-slides.pdf450.16 KB