  In this paper we consider the problems of testing isomorphism of tensors,
$p$-groups, cubic forms, algebras, and more, which arise from a variety of
areas, including machine learning, group theory, and cryptography. These
problems can all be cast as orbit problems on multi-way arrays under different
group actions. Our first two main results are:
  1. All the aforementioned isomorphism problems are equivalent under
polynomial-time reductions, in conjunction with the recent results of
Futorny-Grochow-Sergeichuk (Lin. Alg. Appl., 2019).
  2. Isomorphism of $d$-tensors reduces to isomorphism of 3-tensors, for any $d
\geq 3$.
  Our results suggest that these isomorphism problems form a rich and robust
equivalence class, which we call Tensor Isomorphism-complete, or TI-complete.
We then leverage the techniques used in the above results to prove two
first-of-their-kind results for Group Isomorphism (GpI):
  3. We give a reduction from GpI for $p$-groups of exponent $p$ and small
class ($c < p$) to GpI for $p$-groups of exponent $p$ and class 2. The latter
are widely believed to be the hardest cases of GpI, but as far as we know, this
is the first reduction from any more general class of groups to this class.
  4. We give a search-to-decision reduction for isomorphism of $p$-groups of
exponent $p$ and class 2 in time $|G|^{O(\log \log |G|)}$. While
search-to-decision reductions for Graph Isomorphism (GI) have been known for
more than 40 years, as far as we know this is the first non-trivial
search-to-decision reduction in the context of GpI.
  Our main technique for (1), (3), and (4) is a linear-algebraic analogue of
the classical graph coloring gadget, which was used to obtain the
search-to-decision reduction for GI. This gadget construction may be of
independent interest and utility. The technique for (2) gives a method for
encoding an arbitrary tensor into an algebra.
