On the Complexity of Isomorphism Problems for Tensors, Groups, Polynomials, and Algebras

Two matrices are called equivalent if one can be transformed into the other by multiplying with invertible matrices on the left and right. Extending this idea to 3-tensors, it is natural to define two 3-tensors as isomorphic if they can be transformed into each other by multiplication with three invertible matrices along the three directions.

We show that the problem of testing isomorphism of 3-tensors captures the complexity of testing isomorphism for several algebraic structures, including polynomials, certain families of groups, and associative or Lie algebras. Here “captures” can refer to either polynomial-time equivalence or the containment relation between orbit structures.

This prompts the introduction of a complexity class called Tensor Isomorphism. By varying the underlying fields/rings and group types and actions, Tensor Isomorphism has connections to cryptography (Goldreich—Micali—Wigderson zero-knowledge protocol for isomorphism problems), quantum information, number theory (Bhargava’s approach to Gauss composition law), and geometry (classification of Calabi—Yau threefolds).

Finally, we showcase some recent progress on algorithms for tensor isomorphism over finite fields, which break the decades-old n^log(n) barrier for class-2 p-group isomorphism, a breakthrough initially achieved by Xiaorui Sun.

Based on joint works with Joshua Grochow, Gábor Ivanyos, Xiaorui Sun, Katherine Stange, Yinan Li, Markus Bläser, Antoine Joux, Chuanqi Zhang.