标题： 统计计算复杂度：低次多项式的新见解 显示英文标题

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

摘要： 这是一份关于使用低次多项式预测和解释各种平均情况计算问题中显式统计-计算权衡的调查报告。简而言之，这个框架通过多项式函数必须具有的最低次数来衡量统计任务的复杂性。本调查的主要目标包括：(1) 描述低次框架可以应用的问题类型，涵盖检测（假设检验）、恢复（估计）等问题；(2) 讨论围绕低次下界解释的一些哲学问题，特别是它们在多大程度上应被视为固有计算难度的证据；(3) 探索低次多项式与其它相关方法（如平方和层次结构和统计查询模型）之间的已知联系；以及(4) 给出证明低次下界的数学工具概述。此外，还列出了开放问题清单。 显示英文摘要

摘要： 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. In a nutshell, this framework measures the complexity of a statistical task by the minimum degree that a polynomial function must have in order to solve it. The main goals of this survey are to (1) describe the types of problems where the low-degree framework can be applied, encompassing questions of detection (hypothesis testing), recovery (estimation), and more; (2) discuss some philosophical questions surrounding the interpretation of low-degree lower bounds, and notably the extent to which they should be treated as evidence for inherent computational hardness; (3) explore the known connections between low-degree polynomials and other related approaches such as the sum-of-squares hierarchy and statistical query model; and (4) give an overview of the mathematical tools used to prove low-degree lower bounds. A list of open problems is also included.