<p><strong>Coset Intersection Problem</strong> </p>

<p>Given : $K,H \le S_n$, and $\sigma \in S_n$</p>

<p>Find : $K \cap H\sigma$</p>

<p>Known results are : </p>

<ul>
<li>$n^{O(\sqrt n )}$ time algorithm by L.Babai.</li>
<li>$n^{O(1)} m^{O(\sqrt m )}$, where $m$ is the length of the longest orbits of the two groups by L.Babai.</li>
<li>exp ($O(\sqrt n \ log n))$ by L.Babai.</li>
</ul>

<p>Problem is in $\mathsf{P\text{}}$, if subgroup $K$ is a $S_n$ or just identity element. My question is what are the other cases, where problem is easy to solve i.e. is in $\mathsf{P\text{}}$.</p>

CC BY-SA 3.0
2017-08-30T08:26:02.273Z
Are are aware of the fact that Babai's quasi-polynomial algorithm for graph isomorphism is actually an algorithm for the generalized problem, which is equivalent to the coset intersection problem? Maybe we [should upgrade](https://cstheory.stackexchange.com/questions/19962/consequences-of-a-quasi-polynomial-time-algorithm-for-the-graph-isomorphism-prob/37265#37265) existing practically efficient graph isomorphism algorithms to algorithms for the generalized problem?
Thomas Klimpel
CC BY-SA 3.0
2017-08-30T08:30:15.270Z
Regarding your question itself: [The difficulty of color isomorphism problems is known to be closely linked to the the composition factors of the permutation group involved](https://arxiv.org/abs/1609.08253). So one could give quite a huge list of known "easy" instance, if one wants to.
Thomas Klimpel
<reference-request><graph-isomorphism><gr.group-theory>
Easy instances for coset intersection problem
new
# Easy instances for coset intersection problem

(Asked by: username_0 on 2017-08-30)

**Coset Intersection Problem**

Given : $K,H \le S\_n$, and $\sigma \in S\_n$

Find : $K \cap H\sigma$

Known results are :

* $n^{O(\sqrt n )}$ time algorithm by L.Babai.
* $n^{O(1)} m^{O(\sqrt m )}$, where $m$ is the length of the longest orbits of the two groups by L.Babai.
* exp ($O(\sqrt n \ log n))$ by L.Babai.

Problem is in $\mathsf{P\text{}}$, if subgroup $K$ is a $S\_n$ or just identity element. My question is what are the other cases, where problem is easy to solve i.e. is in $\mathsf{P\text{}}$.

**Tags:** reference-request, graph-isomorphism, gr.group-theory
> **Comments:**
> **username_1**: Are are aware of the fact that Babai's quasi-polynomial algorithm for graph isomorphism is actually an algorithm for the generalized problem, which is equivalent to the coset intersection problem? Maybe we [should upgrade](https://cstheory.stackexchange.com/questions/19962/consequences-of-a-quasi-polynomial-time-algorithm-for-the-graph-isomorphism-prob/37265#37265) existing practically efficient graph isomorphism algorithms to algorithms for the generalized problem?  
> **username_1**: Regarding your question itself: [The difficulty of color isomorphism problems is known to be closely linked to the the composition factors of the permutation group involved](https://arxiv.org/abs/1609.08253). So one could give quite a huge list of known "easy" instance, if one wants to.  

---

## 0 answers

