Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness

A wide range of natural computational problems in computer science, mathematics, physics, and other sciences amounts to deciding if two objects are equivalent. Very often this equivalence is defined in terms of group actions. A natural question is to ask when two objects can be distinguished by polynomial functions that are invariant under the group action. For finite groups, this is just the usual notion of equivalence, but for continuous groups such as the general linear groups it gives rise to a new notion, called orbit closure intersection. This new notion has recently seen substantial interest in the community, as it captures, among others, the graph isomorphism problem, noncommutative polynomial identity testing, null cone problems in invariant theory, equivalence problems for tensor networks, and the classification of multiparty quantum states. Despite remarkable recent algorithmic progress in celebrated special cases, the computational complexity of general orbit closure intersection problems is currently quite unclear. In particular, tensors seem to give rise to the most difficult problems.

In this work we start a systematic study of orbit closure intersection problems from the complexity-theoretic viewpoint.

Our key contributions include:

• We define a complexity class TOCI that captures the power of orbit closure intersection problems for general tensor actions.

• We give an appropriate notion of algebraic reductions that imply polynomial-time reductions in the usual sense, but are amenable to invariant-theoretic techniques.

• We identify several natural tensor problems that are complete for TOCI, one of which is the equivalence of PEPS tensor networks considered by Acuaviva et al (FOCS'23).

• We show that the graph isomorphism problem can be reduced to these complete problems and hence GI ⊆ TOCI. As such, our work establishes the first lower bound on the computational complexity of orbit closure intersection problems, and it explains the difficulty of finding unconditional polynomialtime algorithms beyond special cases, as has been observed in the recent literature.

Index Terms-tensors, orbit closure intersection, equivalence problems, invariants, graph isomorphism

• Left-right action on matrix tuples:

1 More generally, we can allow coordinates from a field F such that its elements can be represented by bitstrings and arithmetic operations on them can be performed efficiently.