<p>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|$ (<a href="https://doi.org/10.1007/978-3-642-31594-7_5" rel="noreferrer">Babai-Codenotti-Qiao</a>, <a href="https://sites.google.com/site/jimmyqiao86/icalp12.pdf?attredirects=0" rel="noreferrer">freely available version</a>), 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.</p>

<p>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 <em>equivalent</em> 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 <a href="http://dx.doi.org/10.1137/1.9781611973082.107" rel="noreferrer">Babai-Codenotti-G.-Qiao</a> or <a href="https://people.cs.uchicago.edu/~laci/students/codenotti.pdf" rel="noreferrer">Codenotti's freely available thesis</a>). 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 <a href="https://doi.org/10.1137/15M1009767" rel="noreferrer">G.-Qiao</a>).</p>

CC BY-SA 4.0
2018-05-06T03:26:02.777Z
2018-05-06T03:26:02.777Z
Joshua Grochow
<p>Isomorphism problems come in several variants: </p>

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

<p>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)}$?</p>

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

CC BY-SA 4.0
2018-05-06T20:14:57.093Z
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: https://arxiv.org/abs/1311.0366 .
Noah Stephens-Davidowitz
CC BY-SA 4.0
2018-05-08T13:19:59.260Z
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
<graph-isomorphism>
Isomorphism Problems with Unknown Single-Exponential Algorithms
verifying
# Isomorphism Problems with Unknown Single-Exponential Algorithms

(Asked by: username_0 on 2018-05-05)

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.

**Tags:** graph-isomorphism

> **Comments:**
> **username_1**: 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: https://arxiv.org/abs/1311.0366 .  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-05-06. Score: 6

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](https://doi.org/10.1007/978-3-642-31594-7_5), [freely available version](https://sites.google.com/site/jimmyqiao86/icalp12.pdf?attredirects=0)), 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](http://dx.doi.org/10.1137/1.9781611973082.107) or [Codenotti's freely available thesis](https://people.cs.uchicago.edu/~laci/students/codenotti.pdf)). 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](https://doi.org/10.1137/15M1009767)).


---

