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

CREATORHe Jia, Aravindan Vijayaraghavan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79843
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.02594

Browse the full library · About the Tower of Babel