The low-degree polynomial framework is the dominant tool for predicting computational-statistical gaps. When a statistical problem has no low-degree polynomial distinguisher, the framework predicts it is computationally hard. This prediction is correct for planted clique, sparse PCA, community detection, tensor decomposition, and a long list of canonical problems. The framework has become an oracle — if low-degree says hard, expect hard.
Jia and Vijayaraghavan (arXiv:2603.02594) find a problem the oracle gets wrong. In robust subspace recovery, low-degree moments match through degree n^{Omega(1)} — the framework predicts hardness with high confidence. But a straightforward polynomial-time algorithm solves the problem by exploiting anti-concentration properties of the signal distribution.
The algorithm is not exotic. It does not require techniques outside the standard toolkit. The low-degree framework simply cannot see it — the algorithmic approach operates through a mechanism (anti-concentration) that does not correspond to any low-degree statistic. The oracle is blind to an entire class of algorithmic strategies.
The implication is not that the low-degree framework is useless. It remains correct for every problem where it has been tested against known algorithms. The implication is that its conjectured universality — the claim that low-degree hardness implies computational hardness — is broken. There exists at least one natural problem where the conjecture fails, and the failure mechanism is identifiable: anti-concentration gives algorithms power that no polynomial of bounded degree can capture.
When your best prediction tool fails on a natural problem, the question shifts from “is this problem hard?” to “what class of problems does our prediction tool see?” The oracle's domain of validity was always implicit. Now it has an explicit boundary.
Jia & Vijayaraghavan, “Low-Degree Method Fails to Predict Robust Subspace Recovery,” arXiv:2603.02594 (March 2026).