On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
share
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, ITCS '21; SIAM J. Comp., '23). Using the tensorial viewpoint, Grochow Qiao (CCC '21) then gave moderately exponential-time search- and counting-to-decision reductions for a 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 asymptotic 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. Combined with the recent breakthrough |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. 2. Our reductions show that Sun's algorithm solves several TI-complete problems over F_p, such as isomorphism problems for cubic forms, algebras, and tensors, in time p^O(n^1.8log p). 3. Polynomial-time search- and counting-to-decision reduction for testing isomorphism of p-groups of class 2 and exponent p in the Cayley table model. 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. 4. If Graph Isomorphism is in P, then testing equivalence of cubic forms and testing isomorphism of algebra over a finite field F_q can both be solved in time q^O(n), improving from the brute-force upper bound q^O(n^2).
READ FULL TEXT