TL;DR
This paper establishes the first algebraic proof complexity bounds for the Tensor Isomorphism (TI) problem, proving that standard algebraic refutation systems like Polynomial Calculus (PC) and Sum-of-Squares (SoS) require linear degree ($\Omega(n)$) to certify non-isomorphism. The authors reveal that PC cannot perform basic linear algebra in sub-linear degree, propose an augmented proof system ($\text{PC+Inv}$) equipped with matrix inversion, and provide an upper bound demonstrating that isomorphism for bounded-rank tensors is tractable.
What Problem Does This Paper Address?
The Tensor Isomorphism (TI) problem asks whether two multi-dimensional arrays (tensors) are equivalent under invertible linear changes of basis. TI sits at the crossroads of quantum information, post-quantum cryptography, and geometric complexity theory, generalizing Graph Isomorphism (GI) while lacking sub-exponential algorithms.
Certifying that two tensors are non-isomorphic translates directly into refuting the solvability of an algebraic system of polynomial equations. A natural algorithmic approach is using Gröbner basis methods or semidefinite programming hierarchies, which are captured proof-theoretically by Polynomial Calculus (PC) and Sum-of-Squares (SoS). The authors set out to answer: How powerful are algebraic and semi-algebraic proof systems when applied to Tensor Isomorphism?
Methods
- Algebraic Reductions in Low Degree: The authors formalize $(d_1, d_2)$-PC reductions between polynomial systems. They show that known combinatorial reductions from Graph Isomorphism to Monomial Code Equivalence, and onward to TI, can be simulated in constant degree ($O(1)$) within PC.
- Direct Reduction from Random 3-XOR: To avoid sparse gadgetry from GI, they construct an alternative reduction mapping Random 3-XOR instances directly to multilinear noncommutative cubic forms and then to tensors, preserving unsatisfiability and proof degrees.
- Proof Complexity of Linear Algebra: By embedding the Functional Pigeonhole Principle ($\text{PHP}^n_r$) into matrix rank equations, they analyze the proof complexity of standard matrix identities in PC.
- Subspace Compression via Inheritance: For bounded-rank tensors, the authors apply the "Inheritance Theorem" to compress $n \times n \times n$ tensors of rank $\le r$ into $O(r^2)$ variables, bounding the refutation degree using Sombra’s Effective Nullstellensatz.
Datasets
Not discussed in the paper. (This work is purely theoretical and does not utilize empirical datasets or benchmarks.)
Key Insights and Ideas
- Linear Algebra is Inherently Hard for PC: Despite linear algebra being an elementary computational tool, PC struggles to verify basic identities. Deriving $BA = I$ from $AB = I$ (the Inversion Principle) or proving that an $n \times r$ matrix cannot invert an $r \times n$ matrix when $r < n$ (the Rank Principle) requires degree $\ge r/2 + 1$.
- The $\text{PC+Inv}$ Proof System: Because tensors are fundamentally multilinear, proof systems tackling TI require linear algebraic reasoning. The authors propose $\text{PC+Inv}$, extending PC with a derivation rule for matrix inversion instances ($AB = I \implies BA = I$), and conjecture that even this augmented system requires $\Omega(n)$ degree for TI.
- Direct Realization of 3-XOR as Tensors: Rather than relying on Cai–Fürer–Immerman (CFI) gadgets, 3-XOR instances naturally correspond to $\{ \pm 1 \}$-diagonal equivalence of cubic forms. Because random hypergraphs lack non-trivial automorphisms, diagonal equivalence coincides with monomial equivalence with high probability.
Key Results
- Degree Lower Bounds for TI:
- Over any field, refuting $n \times n \times n$ Tensor Isomorphism requires $\Omega(n)$ PC degree (and $\Omega(n)$ SoS degree over $\mathbb{R}$) via reduction from GI.
- A direct reduction from Random 3-XOR yields an independent lower bound of $\Omega(n^{1/4})$ PC degree.
- Lower Bounds on Matrix Principles: Refuting $XY = I_n$ (where $X$ is $n \times r$ and $Y$ is $r \times n$ with $r < n$) in PC requires degree $\ge r/2 + 1$. Consequently, deriving $BA = I$ from $AB = I$ requires degree $\ge n/2 + 1$.
- Upper Bounds for Low-Rank Tensors:
- Over any algebraically closed field, refuting isomorphism between two non-isomorphic rank-$\le r$ tensors has Nullstellensatz degree at most $2^{O(r^2)}$.
- Over a finite field $\mathbb{F}_q$ (with field axioms $x^q - x = 0$), the PC degree is at most $O(q r^2)$, implying polynomial-time decidability for constant rank $r$.
Limitations and Future Work
- Lower Bounds for $\text{PC+Inv}$: The authors introduce $\text{PC+Inv}$ to bypass linear algebraic bottlenecks, but proving degree lower bounds for $\text{PC+Inv}$—even for simple candidates like $\mathrm{mod}\text{ }p$ counting principles—remains entirely open.
- The Low-Rank Degree Gap: For rank-$r$ tensors, the upper bound without field equations is exponential in $r^2$ ($2^{O(r^2)}$), leaving a large gap relative to the $\Omega(r^{1/4})$ lower bound.
- Proof Size vs. Degree: Standard size-degree tradeoffs for PC assume Boolean axioms ($x^2 = x$), which TI instances lack. Establishing whether sub-exponential size refutations exist despite polynomial degree lower bounds is an open challenge.
Summary updated