{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib5zflba4ilx2szsy7fjnq7vdvuhq3dactdp3rshfbswlfp5fwz5y",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3miidwl7kmfo2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.00966v1",
  "publishedAt": "2026-04-02T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Runshi Tang",
    "Yuefeng Han",
    "Anru R. Zhang"
  ],
  "textContent": "**Authors:** Runshi Tang, Yuefeng Han, Anru R. Zhang\n\nIn this note, we propose a general framework for proving computational lower bounds in norm approximation by leveraging a reverse detection--estimation gap. The starting point is a testing problem together with an estimator whose error is significantly smaller than the corresponding computational detection threshold. We show that such a gap yields a lower bound on the approximation distortion achievable by any algorithm in the underlying computational class. In this way, reverse detection--estimation gaps can be turned into a general mechanism for certifying the hardness of approximating nontrivial norms. We apply this framework to the spectral norm of order-$d$ symmetric tensors in $\\mathbb{R}^{p^d}$. Using a recently established low-degree hardness result for detecting nonzero high-order cumulant tensors, together with an efficiently computable estimator whose error is below the low-degree detection threshold, we prove that any degree-$D$ low-degree algorithm with $D \\le c_d(\\log p)^2$ must incur distortion at least $p^{d/4-1/2}/\\operatorname{polylog}(p)$ for the tensor spectral norm. Under the low-degree conjecture, the same conclusion extends to all polynomial-time algorithms. In several important settings, this lower bound matches the best known upper bounds up to polylogarithmic factors, suggesting that the exponent $d/4-1/2$ captures a genuine computational barrier. Our results provide evidence that the difficulty of approximating tensor spectral norm is not merely an artifact of existing techniques, but reflects a broader computational barrier.",
  "title": "A General Framework for Computational Lower Bounds in Nontrivial Norm Approximation"
}