  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. 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.8} \log 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\'oran (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)}$.
