On the algebraic proof complexity of Tensor Isomorphism

Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She

Abstract

The Tensor Isomorphism problem (TI) has recently emerged as a central challenge in computational complexity, with connections to group theory, cryptography, and quantum information. Despite its importance, the current best upper bound for TI remains essentially the brute-force algorithm. This paper investigates the power of algebraic and semi-algebraic proof systems—specifically Polynomial Calculus (PC) and Sum of Squares (SoS)—to prove that two non-isomorphic tensors are indeed different. We establish an $\Omega(n)$ lower bound on the PC and SoS degree required for TI, implying that these systems require exponential time to solve the problem. Furthermore, we demonstrate a fundamental weakness in PC: its inability to efficiently perform basic linear algebra, such as deriving $BA=I$ from $AB=I$. To address this, we introduce a stronger system, PC+Inv, and provide a nontrivial upper bound for testing isomorphism in tensors of bounded rank.

Introduction

The Tensor Isomorphism (TI) problem asks whether two 3-dimensional arrays of numbers are equivalent under a change of basis. While its combinatorial relative, Graph Isomorphism (GI), is known to be solvable in quasi-polynomial time, TI is significantly more difficult. It is considered "TI-complete," meaning it captures the complexity of a wide array of problems across mathematics and computer science.

Because TI is fundamentally algebraic, researchers have long speculated whether algebraic proof systems could provide a shortcut to its solution. These systems, such as Polynomial Calculus (PC) and Sum of Squares (SoS), attempt to prove that a system of polynomial equations has no solution. If a proof system can refute an isomorphism in constant degree, the problem can be solved in polynomial time. This work explores the limits of these systems when applied to TI.

Proof Complexity and Algebraic Systems

Proof complexity measures the resources required to prove mathematical statements within a formal system. In the context of TI, we represent the isomorphism condition as a system of polynomial equations. We focus on three primary systems:

  1. Nullstellensatz (NS): A static system where a contradiction is shown by expressing $1$ as a linear combination of the input polynomials.
  2. Polynomial Calculus (PC): A dynamic system that allows for step-by-step reasoning through polynomial addition and multiplication.
  3. Sum of Squares (SoS): A powerful semi-algebraic system that incorporates inequalities and is widely utilized in convex optimization.

To establish lower bounds, we utilize reductions from known hard problems, such as Random 3XOR and Cai–Fürer–Immerman (CFI) gadgets, to show that if TI were easy for these proof systems, these hard problems would be easy as well.

The Linear Algebra Bottleneck

A significant finding of this research is the "linear algebra blind spot" inherent in standard proof systems. We demonstrate that Polynomial Calculus is remarkably inefficient at performing basic matrix operations. Specifically, proving the Rank Principle—that an $n \times r$ matrix cannot have a left inverse if $r < n$—requires a degree proportional to $n$.

Even more striking is the Inversion Principle. In undergraduate linear algebra, it is a basic fact that for square matrices, $AB=I$ implies $BA=I$. However, we prove that any PC derivation of this fact requires a degree of at least $n/2 + 1$. This suggests that the difficulty of TI in these systems may stem from their inability to "understand" the fundamental properties of the matrices that compose tensors.

Main Results

Degree Lower Bounds

We prove an $\Omega(n)$ degree lower bound for refuting Tensor Isomorphism in both PC and SoS. This result is significant because it rules out the possibility of using standard PC or SoS-based algorithms to solve general TI in polynomial time. For these systems, the search for a proof of non-isomorphism is as computationally expensive as brute force.

Bounded Rank Upper Bounds

While general TI is hard, the problem becomes more tractable when the tensors have a low rank ($r$). We provide a Nullstellensatz upper bound of $2^{O(r^2)}$ for tensors of rank $r$. This confirms that for constant-rank tensors, TI can be decided in polynomial time, as the problem reduces to a system with only $O(r^2)$ variables.

The PC+Inv System

To isolate the specific difficulty of TI from the general difficulty of linear algebra, we introduce PC+Inv. This system augments PC with a rule allowing for the immediate substitution of $BA=I$ whenever $AB=I$ is derived. While this system is strictly stronger than PC, we conjecture that TI remains hard even with the power of matrix inversion.

Conclusion and Future Directions

This work establishes that the current most popular algebraic proof systems are insufficient for solving the Tensor Isomorphism problem efficiently. The discovery that PC struggles with basic linear algebra opens new avenues for proof complexity research.

Future work remains to prove lower bounds for the newly proposed PC+Inv system. Additionally, the gap between the current lower bounds and upper bounds for specific tensor ranks remains an open question. Finally, exploring whether "border rank" (the approximative version of tensor rank) allows for similar efficient isomorphism testing could provide further insights into the structural complexity of tensors.

Summary updated

Abstract

The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or rather, proving that two tensors are non-isomorphic) lends itself very naturally to algebraic and semi-algebraic proof systems, such as the Polynomial Calculus (PC) and Sum of Squares (SoS). For its combinatorial cousin Graph Isomorphism, essentially optimal lower bounds are known for approaches based on PC and SoS (Berkholz & Grohe, SODA '17). Our main results are an $\Omega(n)$ lower bound on PC degree or SoS degree for Tensor Isomorphism, and a nontrivial upper bound for testing isomorphism of tensors of bounded rank. We also show that PC cannot perform basic linear algebra in sub-linear degree, such as comparing the rank of two matrices, or deriving $BA=I$ from $AB=I$. As linear algebra is a key tool for understanding tensors, we introduce a strictly stronger proof system, PC+Inv, which allows as derivation rules all substitution instances of the implication $AB=I \rightarrow BA=I$. We conjecture that even PC+Inv cannot solve TI in polynomial time either, but leave open getting lower bounds on PC+Inv for any system of equations, let alone those for TI. We also highlight many other open questions about proof complexity approaches to TI.
BibTeX
@inproceedings{galesi2023algebraic,
  author = {Nicola Galesi and Joshua A. Grochow and Toniann Pitassi and Adrian She},
  title = {{On the algebraic proof complexity of Tensor Isomorphism}},
  booktitle = {CCC},
  year = {2023},
  url = {https://openreview.net/forum?id=AXo2qBVMH5},
}

Loading related content...

Figure