{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiebotjgtweh4qxv6l7n6q4mpa4qh7zxu2jp26qu52yhqzcksip3lu",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mg7eo2ntgfn2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.02594v1",
  "publishedAt": "2026-03-04T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "He Jia",
    "Aravindan Vijayaraghavan"
  ],
  "textContent": "**Authors:** He Jia, Aravindan Vijayaraghavan\n\nThe low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of efficient algorithms for a wide class of high-dimensional statistical problems. We identify a natural and basic hypothesis testing problem in $\\mathbb{R}^n$ which is polynomial time solvable, but for which the low-degree polynomial method fails to predict its computational tractability even up to degree $k=n^{Ω(1)}$. Moreover, the low-degree moments match exactly up to degree $k=O(\\sqrt{\\log n/\\log\\log n})$. Our problem is a special case of the well-studied robust subspace recovery problem. The lower bounds suggest that there is no polynomial time algorithm for this problem. In contrast, we give a simple and robust polynomial time algorithm that solves the problem (and noisy variants of it), leveraging anti-concentration properties of the distribution. Our results suggest that the low-degree method and low-degree moments fail to capture algorithms based on anti-concentration, challenging their universality as a predictor of computational barriers.",
  "title": "Low-Degree Method Fails to Predict Robust Subspace Recovery"
}