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

Imagine trying to find a hidden k -vertex clique (fully connected subgraph) within an otherwise random n -vertex graph (network). While it is possible to find a hidden clique of size k log n by brute-force search, all known "fast" (polynomial-time) algorithms only work if the clique is much larger: k n . Is this an inherent limitation of fast algorithms or should we continue looking for a better one? Similar questions of computational complexity arise in many other statistical settings, such as community detection, clustering, and sparse PCA. While we lack the tools to prove definitively that fast algorithms require k n, this survey describes one sense in which we can prove this threshold is fundamental: all algorithms based on low-degree polynomials -- for instance, counting triangles in the graph would be a degree-3 polynomial -- provably fail (in an appropriate sense) when k n . Furthermore, these low-degree algorithms tend to capture the best tools in our algorithmic toolkit for problems of this style, so finding a fast algorithm for k n would seem to require a major breakthrough or may simply be impossible. This provides a lens for predicting and explaining the limitations of fast algorithms across many different settings.