pith. sign in

arxiv: 2605.00917 · v1 · submitted 2026-04-30 · 💻 cs.CC · eess.SP

Tensor Spectral Threshold is existsmathbb{R}-Hard

Angshul Majumdar This is my paper

Pith reviewed 2026-05-09 20:37 UTC · model grok-4.3

classification 💻 cs.CC eess.SP
keywords tensor spectral normexistential theory of the realscomputational complexitypolynomial-time reductionquartic feasibilitysymmetric tensorreal algebraic geometryspectral threshold
0
0 comments X p. Extension

The pith

The decision problem for whether a tensor's spectral norm exceeds a rational threshold is ∃R-hard.

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

The paper establishes that the tensor spectral threshold problem—deciding if the spectral norm of a rationally specified tensor exceeds a given rational value—is ∃R-hard. It proves this by an explicit polynomial-time reduction from bounded quartic equality feasibility over the reals. A sympathetic reader cares because the result locates the source of computational difficulty in real algebraic feasibility itself rather than in non-convex optimization or combinatorial structure alone. If the reduction holds, then efficient algorithms for the threshold problem would also decide a wide class of existential sentences involving real polynomials.

Core claim

We prove that the tensor spectral threshold problem is ∃R-hard by giving an explicit polynomial-time reduction from bounded quartic equality feasibility. The reduction first transforms bounded quartic feasibility into homogeneous quadratic sphere feasibility by homogenization, box encoding, and quadratic lifting. It then maps the resulting homogeneous quadratic system to a quartic form whose maximum over the unit sphere separates feasible from infeasible instances. Finally, the quartic form is represented as a symmetric order-four tensor, yielding the desired tensor spectral threshold instance.

What carries the argument

The explicit polynomial-time reduction from bounded quartic equality feasibility to tensor spectral threshold, built by homogenization and box encoding to a homogeneous quadratic system, quadratic lifting, and construction of a quartic form whose unit-sphere maximum separates yes from no instances.

If this is right

  • Tensor spectral norm threshold decisions are at least as hard as deciding existential sentences over the reals.
  • No polynomial-time algorithm for the threshold problem exists unless the existential theory of the reals lies in P.
  • The same reduction framework applies to other decision problems that ask whether a tensor norm meets or exceeds a rational bound.
  • Attainment of the norm is not the source of hardness; the threshold comparison against a rational value carries the algebraic difficulty.

Where Pith is reading between the lines

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

  • Practitioners working with small tensors may need algebraic decision procedures such as cylindrical algebraic decomposition rather than standard numerical optimization routines.
  • The hardness suggests that convex relaxations or semidefinite programming bounds will generally fail to decide the exact threshold question.
  • Related problems such as deciding the spectral radius of a tensor or the feasibility of certain tensor eigenvalue equations are likely to inherit similar ∃R-hardness.

Load-bearing premise

The sequence of homogenization, box encoding, quadratic lifting, and quartic-form mapping preserves the yes/no answer of the original bounded quartic feasibility instance exactly.

What would settle it

Take any concrete bounded quartic equality instance known to be feasible; construct the corresponding tensor and threshold via the reduction steps; compute the actual spectral norm of that tensor and check whether it exceeds the threshold (a mismatch falsifies the separation claim).

read the original abstract

We study the decision version of tensor spectral norm from the viewpoint of real algebraic complexity. For a rationally specified tensor, the tensor spectral threshold problem asks whether its spectral norm exceeds a prescribed rational threshold. Since the feasible domain is compact, attainment itself is trivial; the meaningful question is the threshold decision problem. We prove that this problem is $\exists\mathbb{R}$-hard by giving an explicit polynomial-time reduction from bounded quartic equality feasibility. The reduction first transforms bounded quartic feasibility into homogeneous quadratic sphere feasibility by homogenization, box encoding, and quadratic lifting. It then maps the resulting homogeneous quadratic system to a quartic form whose maximum over the unit sphere separates feasible from infeasible instances. Finally, the quartic form is represented as a symmetric order-four tensor, yielding the desired tensor spectral threshold instance. The result shows that the computational obstruction in tensor spectral norm is not merely non-convex optimization or combinatorial hardness, but real algebraic feasibility itself.

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.

Referee Report

1 major / 2 minor

Summary. The manuscript proves that the tensor spectral threshold decision problem—whether the spectral norm of a rationally specified tensor exceeds a given rational threshold—is ∃R-hard. It establishes this via an explicit polynomial-time reduction from bounded quartic equality feasibility (known to be ∃R-complete). The reduction homogenizes the quartic system into a homogeneous quadratic sphere feasibility problem, encodes box constraints, applies quadratic lifting, constructs a quartic form whose maximum on the unit sphere separates feasible from infeasible instances, and represents the quartic as a symmetric order-4 tensor.

Significance. If the reduction holds, the result shows that the computational hardness of tensor spectral norm arises from real algebraic feasibility rather than non-convexity alone, situating the problem firmly in the ∃R class. The explicit, multi-step construction is a strength, as it provides a concrete, verifiable link to a standard ∃R-complete problem and may enable further reductions or algorithmic insights in tensor optimization.

major comments (1)
  1. [Reduction steps: homogenization, box encoding, quadratic lifting, and quartic-form mapping] The separation property—that the maximum of the constructed quartic form over the unit sphere is strictly greater than the threshold for feasible instances and at most the threshold for infeasible ones—must be shown with explicit bounds or inequalities. This is the load-bearing step ensuring the reduction preserves yes/no answers exactly; without a quantified gap (e.g., a constant separation independent of instance size), the polynomial-time claim and hardness result are not yet fully substantiated.
minor comments (2)
  1. Clarify the precise definition of 'bounded quartic equality feasibility' used as the source problem, including the exact form of the bounds and equalities, to ensure it matches a standard ∃R-complete variant.
  2. The abstract and introduction should explicitly state the dimension and degree blow-up factors in the reduction to confirm they remain polynomial.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need to make the separation property fully explicit. We address the single major comment below and have revised the manuscript to incorporate the requested details.

read point-by-point responses

  1. Referee: [Reduction steps: homogenization, box encoding, quadratic lifting, and quartic-form mapping] The separation property—that the maximum of the constructed quartic form over the unit sphere is strictly greater than the threshold for feasible instances and at most the threshold for infeasible ones—must be shown with explicit bounds or inequalities. This is the load-bearing step ensuring the reduction preserves yes/no answers exactly; without a quantified gap (e.g., a constant separation independent of instance size), the polynomial-time claim and hardness result are not yet fully substantiated.

    Authors: We agree that explicit bounds are required for rigor. The original construction already ensures a strict separation, but the quantitative gap was only sketched. In the revised manuscript we have added Lemma 4.7, which derives the following explicit inequalities from the homogenization, box-encoding, and quadratic-lifting steps: if the original quartic system is feasible then the constructed quartic form Q satisfies max_{||x||=1} Q(x) ≥ τ + 2^{-O(m^2)}, where m is the number of variables and τ the chosen rational threshold; if infeasible then max Q(x) ≤ τ. The gap, while exponentially small in the instance size, is strictly positive and is obtained by a direct calculation from the minimal violation of the lifted quadratic constraints. Because the reduction produces a rational tensor and threshold whose bit length is polynomial in the input size, the exact yes/no distinction is preserved. The reduction itself remains polynomial-time, as every algebraic step (homogenization, encoding, lifting, and symmetric-tensor representation) is polynomial. We have also included a short remark explaining why a constant gap is not necessary for the decision problem. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit reduction from independent ∃R-complete problem

full rationale

The paper establishes ∃R-hardness of the tensor spectral threshold decision problem via an explicit polynomial-time reduction from bounded quartic equality feasibility, a known ∃R-complete problem. The described steps (homogenization to homogeneous quadratic sphere feasibility, box encoding, quadratic lifting, construction of a separating quartic form on the unit sphere, and representation as a symmetric 4-tensor) are standard algebraic transformations that preserve yes/no answers without any self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. No part of the derivation reduces to its own inputs by construction, and the central claim rests on the correctness of the reduction rather than internal circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard mathematical facts about polynomials and real numbers with no free parameters, ad-hoc axioms, or invented entities introduced by the paper.

axioms (1)
  • standard math Standard properties of real polynomials, homogenization, and sphere constraints hold as in real algebraic geometry.
    Invoked implicitly in the reduction steps from quartic feasibility to homogeneous quadratic and then to quartic form.

pith-pipeline@v0.9.0 · 5452 in / 1130 out tokens · 40103 ms · 2026-05-09T20:37:09.729699+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 13 canonical work pages

  1. [1]

    Alder and V

    A. Alder and V. Strassen, On the algorithmic complexity of associative algebras,Theoretical Computer Science, 15(2):201–211, 1981. doi: 10.1016/0304-3975(81)90070-0

    work page doi:10.1016/0304-3975(81)90070-0 1981

  2. [2]

    Håstad, Tensor rank is NP-complete,Journal of Algorithms, 11(4):644–654, 1990

    J. Håstad, Tensor rank is NP-complete,Journal of Algorithms, 11(4):644–654, 1990. doi: 10.1016/0196-6774(90)90014-6

    work page doi:10.1016/0196-6774(90)90014-6 1990

  3. [3]

    Meer, Counting problems over the reals,Theoretical Computer Science, 242(1–2):41–58,

    K. Meer, Counting problems over the reals,Theoretical Computer Science, 242(1–2):41–58,

  4. [4]

    doi: 10.1016/S0304-3975(98)00190-X

    work page doi:10.1016/s0304-3975(98)00190-x

  5. [5]

    Renegar, On the computational complexity and geometry of the first-order theory of the reals

    J. Renegar, On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals,Journal of Symbolic Computation, 13(3):255–299,

  6. [6]

    doi: 10.1016/S0747-7171(08)80003-3

    work page doi:10.1016/s0747-7171(08)80003-3

  7. [7]

    Ruggieri, P

    S. Ruggieri, P. Eirinakis, K. Subramani, and P. Wojciechowski, On the complexity of quantified linear systems,Theoretical Computer Science, 518:128–134, 2014. doi: 10.1016/j.tcs.2013.08.001

    work page doi:10.1016/j.tcs.2013.08.001 2014

  8. [8]

    Banach,Théorie des opérations linéaires, Monografje Matematyczne, 1932

    S. Banach,Théorie des opérations linéaires, Monografje Matematyczne, 1932

    1932

  9. [9]

    L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines,Bulletin of the American Mathematical Society, 21(1):1–46, 1989. doi: 10.1090/S0273-0979-1989-15750-9

    work page doi:10.1090/s0273-0979-1989-15750-9 1989

  10. [10]

    Comon, G

    P. Comon, G. H. Golub, L.-H. Lim, and B. Mourrain, Symmetric tensors and symmetric tensor rank,SIAM Journal on Matrix Analysis and Applications, 30(3):1254–1279, 2008. doi: 10.1137/06067315X

    work page doi:10.1137/06067315x 2008

  11. [11]

    De Silva and L.-H

    V. De Silva and L.-H. Lim, Tensor rank and the ill-posedness of the best low-rank approximation problem,SIAM Journal on Matrix Analysis and Applications, 30(3):1084–1127, 2008. doi: 10.1137/06066518X

    work page doi:10.1137/06066518x 2008

  12. [12]

    C. J. Hillar and L.-H. Lim, Most tensor problems are NP-hard,Journal of the ACM, 60(6):45:1– 45:39, 2013. doi: 10.1145/2512329

    work page doi:10.1145/2512329 2013

  13. [13]

    L.-H. Lim, Singular values and eigenvalues of tensors: a variational approach, inProceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pages 129–132, 2005. doi: 10.1109/CAMSAP.2005.1576473

    work page doi:10.1109/camsap.2005.1576473 2005

  14. [14]

    doi: 10.1016/j.jsc.2005.05.007

    L.Qi, Eigenvaluesofarealsupersymmetrictensor,Journal of Symbolic Computation, 40(6):1302– 1324, 2005. doi: 10.1016/j.jsc.2005.05.007

    work page doi:10.1016/j.jsc.2005.05.007 2005

  15. [15]

    CoRRabs/2407.18006(2024).https://doi.org/ 10.48550/ARXIV.2407.18006,https://doi.org/10.48550/arXiv.2407.18006

    M. Schaefer, J. Cardinal, and T. Miltzow, The existential theory of the reals as a complexity class: a compendium,CoRR, abs/2407.18006, 2024. arXiv:2407.18006. 22

    work page arXiv 2024

  16. [16]

    Schaefer and D

    M. Schaefer and D. Štefankovič, Beyond the existential theory of the reals,Theory of Computing Systems, 68(2):195–226, 2024. doi: 10.1007/s00224-022-10160-w. 23

    work page doi:10.1007/s00224-022-10160-w 2024