  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|^{\Theta(\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. 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}\cdot \log q)}$ for cubic form equivalence and
algebra isomorphism.
  3. Polynomial-time search- and counting-to-decision reduction for testing
isomorphism of $p$-groups of class $2$ and exponent $p$ when Cayley tables are
given. This answers questions of Arvind and T\'oran (Bull. EATCS, 2005) for
this group class, thought to be one of the hardest cases of Group Isomorphism.
