Abstract

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.

Attachment

Video Recording