# Isomorphism Problems with Unknown Single-Exponential Algorithms

Isomorphism problems come in several variants:

1. Group isomorphism can be solved in time $n^{O(\log n)}$
2. Graph isomorphism can be solved in time $n^{\log^{O(1)} n}$
3. Isomorphism of linear codes can be solved in time $2^{O(n)}$ ...

Where for each $n$ we assume that an isomorphism is a permutation of the set $\{1,...,n\}$. Is there a well studied variant of isomorphism problem that is known to be solvable in time $2^{O(n\log n)}$ but not in time $2^{O(n)}$?

Obs: Note that $n!\cdot n^{O(1)} = 2^{O(n\log n)}$ is roughly the time necessary to test all permutations.

• The lattice isomorphism problem kind of qualifies in that it has a known 2^{O(n log n)}-time algorithm but no known 2^{O(n)}-time algorithm. But, this is sort of an obnoxious answer because 2^{O(n log n)} is not the time necessary to test all possible isomorphisms. The right analogue of "testing all possible permutations" here is to test all possible permutations between the possibly 2^{O(n)} shortest vectors in the lattice. See Haviv and Regev for more: arxiv.org/abs/1311.0366 . – Noah Stephens-Davidowitz May 6 '18 at 20:14
• Another relevant question you might be interested in is about isomorphism problems where the group is matrices over a finite field instead of permutations. There the analogous question is time $q^{n^2}$ (the order of the group) vs $q^n$. This also shows up in a bunch of places, such as conjugacy of linear spaces of matrices. – Joshua Grochow May 8 '18 at 13:19

A. Permutational isomorphism (aka conjugacy) of permutation groups. Input: Two lists of permutations $\pi_1, \dotsc, \pi_k, \rho_1, \dotsc, \rho_l$ Decide: Is there a permutation $\gamma$ such that $\gamma\langle \pi_1, \dotsc, \pi_k \rangle \gamma^{-1} = \langle \rho_1, \dotsc, \rho_\ell\rangle$, where $\langle \dotsc \rangle$ denotes the subgroup generated by $\dotsc$. The best known running time is $2^{O(n)}|G|$ (Babai-Codenotti-Qiao, freely available version), where the permutations are permutations on $n$ elements and $G = \langle \pi_1, \dotsc, \pi_k \rangle$. Note that $|G|$ can be as large as $n!$, so in the worst case this is $2^{O(n \log n)}$ time. Running time $2^{O(n)}$ (independent of $|G|$) is still open.
B. Group code equivalence for any group other than prime cyclic. For a group $G$, a $G$-code of length $n$ is a subgroup of $G^n$, specified by a generating set. Two such $G$-codes are equivalent if they become equal (as subgroups) after applying a permutation on the $n$ coordinates. For $G = \mathbb{Z}/p\mathbb{Z}$, this is the same as linear code equivalence and can be solved in $2^{O(n)}$ time (Babai; see Babai-Codenotti-G.-Qiao or Codenotti's freely available thesis). However, it is still open even if $G$ is a cyclic $p$-group of non-prime order, such as $\mathbb{Z}/p^2\mathbb{Z}$. Also, even doing the case of cyclic $p$-groups in time $2^{O(n)}$ (with operations in $G$ at unit cost) would have an application (see Observation 7.8 G.-Qiao).