arxiv: 2604.00966 · v2 · submitted 2026-04-01 · 🧮 math.ST · cs.CC· stat.TH

Recognition: 2 theorem links

· Lean Theorem

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation

Runshi Tang , Yuefeng Han , Anru R. Zhang

Authors on Pith no claims yet

Pith reviewed 2026-05-13 21:52 UTC · model grok-4.3

classification 🧮 math.ST cs.CCstat.TH

keywords computational lower boundstensor spectral normlow-degree algorithmsdetection-estimation gapnorm approximationhigh-order tensorslow-degree conjecture

0 comments

The pith

Any low-degree algorithm for the spectral norm of order-d tensors must incur distortion at least p to the power d/4 minus 1/2 up to polylog factors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a framework that converts a reverse detection-estimation gap in a testing problem into lower bounds on how well any algorithm in a given class can approximate a nontrivial norm. If an efficient estimator achieves error below the computational detection threshold for the testing problem, then the same class of algorithms cannot approximate the norm to higher accuracy without large distortion. The authors apply the framework to the spectral norm of symmetric order-d tensors by combining a known low-degree hardness result for detecting nonzero high-order cumulant tensors with an estimator whose error lies below that threshold. This yields the stated distortion lower bound for all degree-D algorithms where D is at most a constant times (log p) squared, with an extension to all polynomial-time methods under the low-degree conjecture. The bound matches known upper bounds up to logarithmic factors in several regimes, indicating that the hardness is intrinsic rather than an artifact of current methods.

Core claim

We propose a framework for proving computational lower bounds in norm approximation by leveraging a reverse detection-estimation gap. Starting from 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. For the spectral norm of order-d symmetric tensors in R^{p^d}, any degree-D low-degree algorithm with D ≤ c_d (log p)^2 must incur distortion at least p^{d/4-1/2} / polylog(p). Under the low-degree conjecture the same conclusion extends to all polynomial-time methods.

What carries the argument

Reverse detection-estimation gap: the existence of an efficient estimator whose error lies below the computational detection threshold for an associated testing problem, which is then converted into a distortion lower bound for norm approximation.

If this is right

The exponent d/4-1/2 represents a genuine computational barrier for approximating the tensor spectral norm.
In several important regimes the lower bound matches the best known upper bounds up to polylog factors.
Under the low-degree conjecture the same distortion barrier applies to every polynomial-time algorithm.
The computational difficulty of tensor spectral norm approximation is not merely an artifact of existing techniques.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The reverse-gap technique could be applied to other norms whenever a suitable testing problem and sub-threshold estimator can be identified.
Algorithms outside the low-degree polynomial class would be needed to beat the stated distortion bound.
If the low-degree conjecture turns out to be false, polynomial-time methods might still achieve better approximation than the current barrier predicts.

Load-bearing premise

An efficiently computable estimator exists whose error for the underlying testing problem lies below the low-degree detection threshold.

What would settle it

An explicit degree-D algorithm with D ≤ c_d (log p)^2 that approximates the tensor spectral norm to distortion o(p^{d/4-1/2} / polylog(p)) would disprove the claimed lower bound.

read the original abstract

In this note, we propose a 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper turns a reverse detection-estimation gap into a general tool for lower bounds on norm approximation and gets matching hardness results for tensor spectral norms.

read the letter

The main point is that the authors show how to convert a gap where you can estimate better than you can detect into a lower bound on approximation distortion for nontrivial norms. They apply this to the spectral norm of order-d symmetric tensors and obtain that any low-degree algorithm of degree at most c_d (log p)^2 must suffer distortion at least p^{d/4 - 1/2} over polylog p. Under the low-degree conjecture this extends to all polynomial-time algorithms, and in several regimes it matches the best known upper bounds up to logs. That suggests the exponent is a real computational barrier rather than just a limitation of current methods. The framework itself is the new piece: it packages the reverse gap as a reusable mechanism that starts from an existing testing hardness result and an efficient estimator below the detection threshold. The logic follows directly from the cited low-degree result on cumulant tensor detection without obvious circularity or extra assumptions beyond the standard conjecture. The argument is clean and the application is direct. The soft spots are limited. The estimator construction and the precise error comparison to the detection threshold need to be checked in the full text to confirm the constants work out, but the abstract sketch is consistent. The polylog factors and the dependence on d are standard and not a major issue. This is for people working on computational lower bounds in high-dimensional statistics and tensor methods. A reader who follows low-degree techniques or approximation hardness in data science will find the general device useful. It deserves a serious referee because the chain is coherent, the bounds are tight against known algorithms, and the framework is reusable.

Referee Report

2 major / 2 minor

Summary. The paper introduces a framework that converts a reverse detection-estimation gap into computational lower bounds for approximating nontrivial norms. For the spectral norm of order-d symmetric tensors in R^{p^d}, it combines a cited low-degree hardness result for detecting nonzero high-order cumulant tensors with an efficiently computable estimator whose error lies below the detection threshold. This yields that any degree-D low-degree algorithm with D ≤ c_d (log p)^2 incurs distortion at least p^{d/4-1/2}/polylog(p); under the low-degree conjecture the bound extends to all polynomial-time algorithms. The lower bound matches known upper bounds up to polylog factors in several regimes.

Significance. If the framework and its application hold, the work supplies a general mechanism for proving hardness of norm approximation via existing detection results, with the tensor spectral norm serving as a concrete case where the exponent d/4-1/2 appears to be a genuine computational barrier rather than an artifact of current techniques. The explicit matching with upper bounds strengthens the claim that the result captures an intrinsic limitation.

major comments (2)

[§3] §3 (General Framework): The reduction from a reverse detection-estimation gap to the distortion lower bound is stated at a high level; the precise translation of the estimator error into the approximation factor (including how the polylog(p) terms arise) must be written out explicitly with all constants tracked, as this step is load-bearing for the claimed p^{d/4-1/2} exponent.
[§4] §4 (Tensor Spectral Norm Application): The manuscript invokes an 'efficiently computable estimator' whose error is below the low-degree detection threshold for cumulant tensors, but does not supply the explicit construction or the quantitative error bound (e.g., the precise o(threshold) rate). Without this, the gap that produces the distortion lower bound cannot be verified.

minor comments (2)

[Theorem 1] The dependence of the constant c_d on the tensor order d should be stated explicitly in the statement of the main theorem, rather than left implicit in the degree bound D ≤ c_d (log p)^2.
[Introduction] Notation for the spectral norm ||·||_σ and the cumulant tensor detection problem should be introduced once in a dedicated notation paragraph to avoid repeated re-definition across sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments correctly identify places where the current manuscript is too terse. We will revise the paper to supply the requested explicit derivations, constructions, and constant tracking. Below we respond point by point.

read point-by-point responses

Referee: [§3] §3 (General Framework): The reduction from a reverse detection-estimation gap to the distortion lower bound is stated at a high level; the precise translation of the estimator error into the approximation factor (including how the polylog(p) terms arise) must be written out explicitly with all constants tracked, as this step is load-bearing for the claimed p^{d/4-1/2} exponent.

Authors: We agree that the argument in §3 is presented at too high a level. In the revised manuscript we will expand the proof of the general framework into a self-contained derivation. Starting from a testing problem with computational detection threshold τ and an estimator with error ε ≪ τ, we will show that any algorithm in the given computational class must incur distortion at least τ/ε (up to universal constants). We will track every constant explicitly, including the factors that produce the polylog(p) terms when the framework is instantiated with the low-degree threshold for cumulant tensors. The resulting bound will be stated with the precise exponent d/4−1/2 and the explicit polylog(p) denominator. revision: yes
Referee: [§4] §4 (Tensor Spectral Norm Application): The manuscript invokes an 'efficiently computable estimator' whose error is below the low-degree detection threshold for cumulant tensors, but does not supply the explicit construction or the quantitative error bound (e.g., the precise o(threshold) rate). Without this, the gap that produces the distortion lower bound cannot be verified.

Authors: We acknowledge that the current version only cites the existence of the estimator without giving its construction or a quantitative error analysis. The estimator is a simple, linear-time average of suitably normalized monomials; its error is O(p^{-c}) for a positive constant c that is strictly smaller than the low-degree detection threshold (which is of order p^{-d/4+1/2} up to logs). In the revision we will include the full definition of the estimator, a complete proof that its error lies below the cited low-degree threshold by a factor sufficient to recover the claimed distortion, and the precise o(·) rate. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent cited hardness result

full rationale

The paper's central derivation converts an external low-degree hardness result for cumulant tensor detection (cited as recently established) plus an efficiently computable estimator into a distortion lower bound via the reverse detection-estimation gap framework. No equation in the provided text reduces the claimed bound to a fitted parameter, self-definition, or self-citation chain internal to this manuscript. The low-degree conjecture extension is stated conditionally and does not alter the independence of the cited detection threshold. This matches the default expectation of a self-contained argument against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the low-degree conjecture for extending hardness to polynomial time and on the existence of an estimator with error below the detection threshold; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Low-degree conjecture: low-degree algorithms capture the hardness of the detection problem for nonzero high-order cumulant tensors
Invoked to extend the distortion lower bound from degree-D algorithms to all polynomial-time algorithms.

pith-pipeline@v0.9.0 · 5570 in / 1316 out tokens · 40767 ms · 2026-05-13T21:52:43.954160+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1... inf γ_f ≥ D_det / (4 D_est(bμ_p))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

and Naor, A

Alon, N. and Naor, A. (2006). Approximating the cut-norm via grothendieck’s inequality.SIAM Journal on Computing, 35(4):787–803. Bhattiprolu, V., Ghosh, M., Guruswami, V., Lee, E., and Tulsiani, M. (2017a). Weak decou- pling, polynomial folds, and approximate optimization over the sphere. In58th Annual IEEE Symposium on Foundations of Computer Science (FO...

work page arXiv 2006
[2]

Harrow, A

PMLR. Harrow, A. W. and Montanaro, A. (2013). Testing product states, quantum Merlin-Arthur games and tensor optimization.Journal of the ACM, 60(1):3:1–3:43. He, S., Hu, H., Jiang, B., and Li, Z. (2023). Approximating Tensor Norms via Sphere Covering: Bridging the Gap Between Primal and Dual. arXiv:2302.14219 [math]. Hillar, C. J. and Lim, L.-H. (2013). M...

work page arXiv 2013