On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications

Many isomorphism problems for tensors, groups, algebras, and polynomials were recently shown to be equivalent to one another under polynomial-time reductions, prompting the introduction of the complexity class TI (Grochow & Qiao, SIAM J. Comp. '23 & ITCS '21). Using the tensorial viewpoint, Grochow & Qiao (ACM Trans. Comput. Theory, '24 & CCC '21) gave moderately exponential-time search-and counting-to-decision reductions for some class of p-groups. A significant issue was that the reductions usually incurred a quadratic increase in the length of the tensors involved. When the tensors represent p-groups, this corresponds to an increase in the order of the group of the form |G| Θ(log |G|) , negating any gains in the Cayley table model. In this paper, we present a new kind of tensor gadget that allows us to replace those quadratic-length reductions with linear-length ones, yielding the following consequences: 1. If Graph Isomorphism is in P, then testing equivalence of cubic forms in n variables over F q , and testing isomorphism of n-dimensional algebras over F q , can both be solved in time q O(n) , improving from the brute-force upper bound q O(n 2 ) for both of these. 2. Combined with the |G| O((log |G|) 5/6 ) -time isomorphism-test for p-groups of class 2 and exponent p (Sun, STOC '23), our reductions extend this runtime to p-groups of class c and exponent p where c < p, and yield algorithms in time q O(n 1.8 •log q) for cubic form equivalence and algebra isomorphism. 3. Polynomial-time search-and counting-to-decision reduction for testing isomorphism of pgroups of class 2 and exponent p when Cayley tables are given. This answers questions of Arvind and Tóran (Bull. EATCS, 2005) for this group class, thought to be one of the hardest cases of Group Isomorphism. Our reductions are presented in a more modular and composable fashion compared to previous gadgets, making them easier to reason about and, crucially, easier to combine. The results are also used by Ivanyos-Mendoza-Qiao-Sun-Zhang to simplify the algorithm in (Sun, STOC '23) and extend to more general p-groups.