![Geometry and Computation in High Dimensions.png](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-05/Geometry%20and%20Computation%20in%20High%20Dimensions.png.jpg?itok=1JtiYLWR)
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.