3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 . $\endgroup$ – Noah Stephens-Davidowitz May 6 '18 at 20:14
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow May 8 '18 at 13:19
6
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.