Low-Degree Method Fails to Predict Robust Subspace Recovery
He Jia, Aravindan Vijayaraghavan · 2026
Read Low-Degree Method Fails to Predict Robust Subspace Recovery by He Jia, Aravindan Vijayaraghavan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-02594.txt.
Description
He Jia and Aravindan Vijayaraghavan challenge a popular hardness predictor in this 2026 paper. The low-degree method predicts which high-dimensional problems efficient algorithms can solve. Its success bred a conjecture that it captures algorithmic power broadly. Robust subspace recovery is their test case, a basic problem of finding a hidden subspace amid outliers.
For one natural testing version, the pattern of low-degree moments looks hard up to high degree. That suggests no fast algorithm should exist. Yet the authors give a simple, robust polynomial-time algorithm that solves it. Their method exploits anti-concentration, a property the low-degree lens misses. Noise-tolerant variants fall to the same approach. Universality claims for the low-degree framework thus need revision.
Catalog record
| CREATOR | He Jia, Aravindan Vijayaraghavan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79843 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.02594