Low-Degree Method Fails to Predict Robust Subspace Recovery

He Jia, Aravindan Vijayaraghavan

The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machin…