论文标题
对低度猜想的反例
Counterexamples to the Low-Degree Conjecture
论文作者
论文摘要
霍普金斯（Hopkins）（2018）的一种猜想认为，对于某些高维假设检验问题，任何多项式时间算法都无法胜过所谓的“简单统计量”，这些“简单统计量”是数据中低维多项式的。这种猜想正式围绕着最近的一系列工作的信念，这些工作旨在通过低度的似然比来理解统计与竞争性的权衡。在这项工作中，我们驳斥了霍普金斯的猜想。但是，我们的反示例至关重要地利用了猜想中使用的噪声算子的细节，我们指出了一种修改猜想以排除我们的反例的简单方法。我们还举了一个例子，说明（即使在上述修改之后），猜想中的对称性假设也是必要的。这些结果不会破坏计算下限的低度框架，而是旨在更好地了解其适用的类别。
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to.
