∃ ℝ \exists\mathbb{R} -Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants

Angshul Majumdar · 2026

Read ∃ ℝ \exists\mathbb{R} -Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants by Angshul Majumdar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17061.txt.

Introduction

Majumdar studies the complexity of singularity for multilinear maps, where the determinant's higher cousin exists only in boundary format and grows messy fast. He proves tensor degeneracy is complete for ∃R, via an exact algebraic chain with no added tricks. In boundary format, the two coincide, while deterministic hardness transfer reduces to a polynomial identity test.

Catalog record

CREATORAngshul Majumdar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24669
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2604.17061

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

∃ ℝ \exists\mathbb{R} -Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants Angshul Majumdar 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 ∃ ℝ \exists\mathbb{R} -completeness, while the deterministic complexity of hyperdeterminant vanishing remains tied to a derandomization problem in algebraic complexity. 1 Introduction The determinant is the fundamental algebraic certificate of singularity in linear algebra: for a square matrix M , the condition \det(M)=0 is equivalent to the existence of a nonzero vector in the kernel of M . In multilinear algebra, the corresponding situation is subtler. Tensors admit an intrinsic notion of singularity, usually called degeneracy , defined by the existence of nonzero vectors whose modewise contractions vanish simultaneously. In boundary format, this condition is captured by the hyperdeterminant, the classical multilinear analogue of the determinant introduced by Cayley and developed systematically by Gelfand, Kapranov, and Zelevinsky [ 1 , 2 ] . Outside boundary format, however, degeneracy remains meaningful while the hyperdeterminant is unavailable as a single polynomial certificate. This distinction motivates the central question of the present paper: what is the computational complexity of tensor singularity in its intrinsic form? Our answer is that the right computational primitive is not hyperdeterminant vanishing, but degeneracy itself. Our contributions. We show that tensor degeneracy is the natural computational analogue of matrix singularity in multilinear algebra, and prove that deciding degeneracy of real 3-tensors is \exists\mathbb{R} -complete. The reduction is exact and entirely algebraic: homogeneous quadratic feasibility is reduced to projective bilinear feasibility, then to singular matrix-pencil feasibility, and finally to tensor degeneracy, without combinatorial gadgets or relaxation. We then isolate the exact gap between intrinsic tensor singularity and its classical polynomial certificate. In boundary format, degeneracy is equivalent to hyperdeterminant vanishing, so transferring hardness requires a deterministic boundary-format lifting. We show that every known route to such a lifting reduces to finding a nonzero evaluation point for a completion polynomial, yielding a structured polynomial identity testing problem. Thus tensor degeneracy is characterized at the level of \exists\mathbb{R} -completeness, whereas the deterministic complexity of hyperdeterminant vanishing is blocked by a derandomization problem in algebraic complexity. The class \exists\mathbb{R} captures decision problems reducible to the solvability of systems of polynomial equations and inequalities over \mathbb{R} , and is the natural complexity class for problems in real algebraic geometry [ 6 ] . Our result places tensor degeneracy alongside the standard semialgebraic feasibility problems that define this class. At the same time, it separates degeneracy from other tensor hardness phenomena. Many tensor problems are known to be NP-hard, including eigenvalue, singular value, and best rank-one approximation problems [ 3 ] . Tensor rank is also computationally hard in a strong algebraic sense [ 4 ] . However, these problems do not isolate singularity itself. Degeneracy does. A second theme of the paper concerns the hyperdeterminant. In boundary format, it gives a polynomial certificate for degeneracy, but all known hardness transfers to that setting use randomized completions [ 7 ] . We explain why deterministic lifting is difficult: it requires selecting a point outside the zero set of a completion polynomial attached to the input tensor. This yields a structured polynomial identity testing problem for a family of hyperdeterminant circuits. In this sense, the gap between degeneracy and hyperdeterminant vanishing is not merely geometric; it is a derandomization problem. This suggests that, in contrast to linear algebra where a single polynomial captures singularity, the multilinear setting separates into an intrinsic geometric condition (degeneracy) and a restricted polynomial certificate (the hyperdeterminant), whose computational connection remains unresolved. Organization. Section 2 positions the work relative to tensor complexity and hyperdeterminants. Section 3 develops the hardness source through quadratic, bilinear, and singular pencil feasibility. Section 4 proves the main theorem that real 3-tensor degeneracy is \exists\mathbb{R} -complete. Section 5 explains boundary format and the relation to hyperdeterminant vanishing. Section 6 isolates the structured polynomial identity testing barrier. Section 7 formalizes the failure of natural deterministic boundary-lifting strategies. Section 8 concludes with insights and open problems. 2 Related Work The hyperdeterminant was developed systematically by Gelfand, Kapranov, and Zelevinsky, who showed that in boundary format it defines the dual variety to the Segre embedding and vanishes exactly on degenerate tensors [ 1 ] . In that sense it is the canonical polynomial analogue of the determinant in multilinear algebra. However, unlike the determinant, it exists only in boundary format and becomes rapidly unwieldy even in modest dimensions [ 1 , 2 ] . Recent work has shown that testing hyperdeterminant vanishing is NP-hard in dimension four and higher, using randomized boundary-format embeddings [ 7 ] . Our work does not extend that hardness result to \exists\mathbb{R} -hardness; rather, it identifies the exact unrestricted multilinear primitive underlying it, namely tensor degeneracy. On the complexity side, \exists\mathbb{R} is now understood as the natural class for semialgebraic feasibility problems. Standard compendia and surveys record the \exists\mathbb{R} -completeness of homogeneous quadratic feasibility and related degree-two formulations [ 6 ] . This is the algebraic starting point for our reductions. Our use of bilinearization is therefore not a gadget construction but a direct multilinear normal-form reduction. More broadly, tensors exhibit pervasive hardness phenomena. Eigenvalue, singular value, best rank-one approximation, and many other tensor tasks are NP-hard [ 3 ] . Tensor rank is also complete for the existential theory of the base field in a strong sense [ 4 ] . Those results, however, do not isolate singularity itself. The contribution of the present paper is to show that the intrinsic geometric notion of degeneracy already has full \exists\mathbb{R} -hardness. A second relevant line of work concerns arithmetic descriptions of hyperdeterminants. Boundary-format hyperdeterminants admit determinantal or circuit representations; recent work of Joux and Narayanan gives explicit arithmetic circuits for families of hyperdeterminants, with quasipolynomial to subexponential complexity depending on the format family [ 8 ] . This is exactly what turns the missing deterministic lifting step into a structured PIT problem rather than merely a geometric completion problem. Finally, the derandomization issue connects with the general PIT landscape. Kabanets and Impagliazzo showed that deterministic polynomial-time PIT for general arithmetic circuits would imply major Boolean or arithmetic circuit lower bounds [ 5 ] . We do not claim such consequences for the hyperdeterminant family considered here; however, the comparison is instructive. The only gap between unrestricted

Read the complete text