pith. sign in

arxiv: 2604.17061 · v1 · submitted 2026-04-18 · 💻 cs.CC

existsmathbb{R}-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants

Angshul Majumdar This is my paper

Pith reviewed 2026-05-10 06:20 UTC · model grok-4.3

classification 💻 cs.CC
keywords tensor degeneracyexistential theory of the realshyperdeterminantalgebraic complexityderandomizationpolynomial identity testingmultilinear maps
0
0 comments X

The pith

Tensor degeneracy is ∃ℝ-complete via an exact algebraic reduction chain that separates it from hyperdeterminant vanishing.

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

The paper shows that deciding whether a multilinear map given by a tensor is degenerate is complete for the existential theory of the reals. It does so by composing three algebraic reductions that start from homogeneous quadratic feasibility, pass through projective bilinear feasibility and singular matrix-pencil feasibility, and end at tensor degeneracy, all without combinatorial gadgets. In boundary format the two notions coincide because degeneracy equals hyperdeterminant vanishing, but outside that format the hyperdeterminant is only a specific polynomial certificate whose zero set matches the degeneracy locus only after choosing a point outside a completion polynomial. This matters because it places the intrinsic singularity of tensors at the same decision complexity as other real-algebraic problems while showing that any deterministic algorithm for the hyperdeterminant must solve a structured instance of polynomial identity testing.

Core claim

The central claim is that tensor degeneracy—the condition that the associated multilinear map has a nontrivial kernel in projective space—is ∃ℝ-complete. The proof is a chain of exact algebraic equivalences: homogeneous quadratic feasibility reduces to projective bilinear feasibility, which reduces to singular matrix-pencil feasibility, which is directly encoded as the degeneracy of a constructed tensor. In boundary format this degeneracy is identical to the vanishing of the hyperdeterminant. Therefore deterministic hardness for deciding hyperdeterminant vanishing reduces to the problem of finding a point outside the zero set of a certain completion polynomial, which is a structured PIT task

What carries the argument

The exact algebraic reduction chain from homogeneous quadratic feasibility through bilinear forms and matrix pencils to tensor degeneracy, which preserves feasibility equivalence at each step.

If this is right

  • Deciding 3-tensor degeneracy is ∃ℝ-complete.
  • In boundary format, deciding hyperdeterminant vanishing is also ∃ℝ-complete up to selection of a point outside the completion polynomial zero set.
  • Any deterministic algorithm for hyperdeterminant vanishing must solve a structured polynomial identity testing instance.
  • Natural deterministic embedding strategies for transferring hardness to the hyperdeterminant fail.

Where Pith is reading between the lines

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

  • Similar exact algebraic reductions may establish ∃ℝ-completeness for other geometric properties of tensors such as rank or border rank.
  • The identified PIT barrier suggests that derandomization progress in algebraic complexity would directly yield deterministic algorithms for hyperdeterminant vanishing.
  • Tensor degeneracy problems arising in applications may remain hard even when the hyperdeterminant is unavailable as a certificate.

Load-bearing premise

The algebraic reductions preserve exact feasibility equivalence without introducing or losing solutions, and degeneracy coincides with hyperdeterminant vanishing precisely when the tensor is in boundary format.

What would settle it

An explicit 3-tensor constructed from a known ∃ℝ-hard quadratic instance for which one can verify by direct computation that degeneracy holds if and only if the original quadratic system is feasible.

read the original abstract

We study the computational complexity of singularity for multilinear maps. While the determinant characterizes singularity for matrices, its multilinear analogue -- the hyperdeterminant -- is defined only in boundary format and quickly becomes algebraically unwieldy. We show that the intrinsic notion of tensor singularity, namely degeneracy, is complete for the existential theory of the reals. The reduction is exact and entirely algebraic: homogeneous quadratic feasibility is reduced to projective bilinear feasibility, then to singular matrix-pencil feasibility, and finally encoded directly as tensor degeneracy. No combinatorial gadgets are used. In boundary format, degeneracy coincides with hyperdeterminant vanishing. We therefore isolate the exact gap between intrinsic tensor singularity and its classical polynomial certificate. We show that deterministic hardness transfer to the hyperdeterminant reduces to selecting a point outside the zero set of a completion polynomial, yielding a structured instance of polynomial identity testing. We further formalize the failure of several natural deterministic embedding strategies. This identifies a sharp frontier: real 3-tensor degeneracy is fully characterized at the level of \(\ER\)-completeness, while the deterministic complexity of hyperdeterminant vanishing remains tied to a derandomization problem in algebraic complexity.

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

2 major / 2 minor

Summary. The paper claims that deciding degeneracy of 3-tensors is ∃ℝ-complete via an exact algebraic reduction chain with no combinatorial gadgets: homogeneous quadratic feasibility reduces to projective bilinear feasibility, then to singular matrix-pencil feasibility, and finally to tensor degeneracy. In boundary format, degeneracy coincides with hyperdeterminant vanishing. It further shows that deterministic hardness for hyperdeterminant vanishing reduces to a structured polynomial identity testing instance and formalizes the failure of several natural deterministic embedding strategies, establishing a sharp separation between the ∃ℝ-completeness of intrinsic tensor singularity and the derandomization barrier for its classical polynomial certificate.

Significance. If the reductions hold exactly, the result is significant for algebraic complexity theory: it supplies a natural, gadget-free ∃ℝ-complete problem in multilinear algebra and cleanly isolates the gap between tensor degeneracy and the hyperdeterminant. The algebraic (rather than combinatorial) nature of the chain and the explicit reduction of deterministic hyperdeterminant hardness to PIT are notable strengths that would advance understanding of real algebraic decision problems and derandomization barriers.

major comments (2)
  1. [Abstract / Reduction Chain (presumably §3)] The load-bearing step is the first reduction (homogeneous quadratic feasibility to projective bilinear feasibility). The manuscript asserts the reductions are 'exact and entirely algebraic' with no extraneous real solutions, but the skeptic correctly flags that projective embeddings and bilinear encodings can alter real solution sets via scaling freedoms or sign patterns. Explicit verification that the encoding maps are bijective on real feasible instances (including handling of homogeneous scalings and sign consistency) is required; without it, hardness transfer fails even if later steps are faithful. This should be addressed with a dedicated subsection or lemma detailing the real-solution correspondence.
  2. [Boundary Format Discussion (presumably §4)] The claim that 'degeneracy coincides with hyperdeterminant vanishing' in boundary format is used to isolate the exact gap, but the manuscript must confirm that this coincidence holds without additional conditions on the format or field characteristic, as the hyperdeterminant is defined only in boundary format and the degeneracy notion is intrinsic.
minor comments (2)
  1. [Abstract] The abstract and introduction would benefit from a short diagram or table summarizing the four-stage reduction chain and the precise feasibility-preserving maps at each step.
  2. [Derandomization Barrier Section] Notation for the tensor formats and the 'completion polynomial' in the PIT reduction should be introduced with explicit definitions before use in the derandomization barrier argument.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the reduction chain and boundary-format discussion. We address each major point below and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: The load-bearing step is the first reduction (homogeneous quadratic feasibility to projective bilinear feasibility). The manuscript asserts the reductions are 'exact and entirely algebraic' with no extraneous real solutions, but the skeptic correctly flags that projective embeddings and bilinear encodings can alter real solution sets via scaling freedoms or sign patterns. Explicit verification that the encoding maps are bijective on real feasible instances (including handling of homogeneous scalings and sign consistency) is required; without it, hardness transfer fails even if later steps are faithful. This should be addressed with a dedicated subsection or lemma detailing the real-solution correspondence.

    Authors: We agree that an explicit bijectivity argument would improve clarity. The reduction is constructed so that projectivization quotients out homogeneous scalings exactly and the bilinear map preserves the sign patterns of the original quadratic forms, introducing no extraneous real solutions. In the revision we will add a dedicated Lemma (new Lemma 3.2 in §3) that formally proves the maps are bijective on the real feasible sets, handling scalings via the projective space and sign consistency via the homogeneous quadratic structure. This will make the exactness fully transparent. revision: yes

  2. Referee: The claim that 'degeneracy coincides with hyperdeterminant vanishing' in boundary format is used to isolate the exact gap, but the manuscript must confirm that this coincidence holds without additional conditions on the format or field characteristic, as the hyperdeterminant is defined only in boundary format and the degeneracy notion is intrinsic.

    Authors: The equivalence is a standard fact: over any field of characteristic zero (hence over the reals), a tensor in boundary format is degenerate if and only if its hyperdeterminant vanishes. Degeneracy is the intrinsic geometric notion (nontrivial kernel in the multilinear sense), while the hyperdeterminant supplies the polynomial certificate precisely when the format is boundary. We will insert a short clarifying paragraph in §4 stating that the equivalence requires only the boundary-format hypothesis and char 0, with no further restrictions. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit reductions from known ∃ℝ-complete problems

full rationale

The paper's central result is ∃ℝ-completeness of tensor degeneracy via an explicit chain of algebraic reductions starting from homogeneous quadratic feasibility (a known ∃ℝ-complete problem). The steps are described as homogeneous quadratic feasibility reduced to projective bilinear feasibility, then to singular matrix-pencil feasibility, and finally encoded as tensor degeneracy, with the claim that the reductions are exact, entirely algebraic, and use no combinatorial gadgets. Degeneracy coinciding with hyperdeterminant vanishing in boundary format is presented as a direct statement rather than a derived equivalence that loops back to the target. The derandomization barrier is reduced to a polynomial identity testing instance, which is an independent algebraic complexity question. No equations, definitions, or claims in the provided text reduce the result to quantities defined in terms of the target itself, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation is self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard definitions of ∃ℝ, projective varieties, and polynomial feasibility; no new constants, fitted parameters, or postulated entities are introduced.

axioms (1)
  • standard math Standard properties of the existential theory of the reals and algebraic geometry over algebraically closed fields
    Invoked to justify that the chained reductions preserve feasibility exactly.

pith-pipeline@v0.9.0 · 5509 in / 1450 out tokens · 95197 ms · 2026-05-10T06:20:08.278616+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

8 extracted references · 8 canonical work pages

  1. [1]

    I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky.Discriminants, Resultants, and Multidimensional Determinants. Birkh"auser, 1994

    work page 1994

  2. [2]

    Zelevinsky

    A. Zelevinsky. Hyperdeterminants of format2×2×nand boundary format.Annales de l’Institut Fourier, 46(3):591–605, 1996

    work page 1996

  3. [3]

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

    work page 2013

  4. [4]

    Štefankovič and M

    D. Štefankovič and M. Schaefer. The complexity of tensor rank.Theory of Computing Systems, 57(2):407–427, 2015

    work page 2015

  5. [5]

    Kabanets and R

    V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. InProceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 355–364, 2004

    work page 2004

  6. [6]

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

    M. Schaefer et al. The Existential Theory of the Reals as a Complexity Class: A Compendium. arXiv:2407.18006, 2024

    work page arXiv 2024

  7. [7]

    Narayanan

    H. Narayanan. On the complexity of hyperdeterminants.Electronic Colloquium on Computa- tional Complexity (ECCC), TR25-131, 2025. 9

    work page 2025

  8. [8]

    Joux and A

    A. Joux and A. K. Narayanan. A high dimensional Cramer’s rule connecting homogeneous mul- tilinear equations to hyperdeterminants.Electronic Colloquium on Computational Complexity (ECCC), TR24-122, 2024. 10

    work page 2024