Abstract

Isomorphism of tensors is a basic notion in algebraic complexity. Recently, Grochow and Qiao uncovered connections between tensor isomorphism and isomorphism problems for groups, algebras, and polynomials, leading to the formulation of the Tensor Isomorphism complexity class. By varying the groups, actions, and underlying fields or rings, tensor isomorphism problems give rise to many connections and exhibit a range of complexity behaviours. For example:
1. Over finite fields, tensor isomorphism, like Graph Isomorphism, lies in NP ∩ coAM. Complexity reductions around tensor isomorphism play a key role in recent progress on Group Isomorphism (Ivanyos–Mendoza–Qiao–Sun–Zhang, FOCS 2024).
2. Over C, tensor isomorphism is in AM (Koiran, J. Complex.). Tensor isomorphism under unitary and orthogonal group actions naturally appears as an orbit-closure intersection problem.
3. Over Z, tensor isomorphism is decidable (Grunewald–Segal, Ann. Math., 1980). The 2×2×2 case over Z is central to Bhargava’s formulation of higher Gauss composition laws (Ann. Math., 2004), which in turn leads to a quantum polynomial-time algorithm via Hallgren’s algorithm for principal ideal testing (J. ACM, 2007).

Based on joint works with Josh Grochow, Kate Stange, Xiaorui Sun.

Video Recording