Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Alexander S. Wein

This is a survey on the use of low-degree polynomials to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems. I…