<p>Certainly there has been tons of progress! (And if you really meant to ask about the last <em>50</em> years, then that includes the algorithms of Schreier-Sims and Butler that you already mentioned...)</p>

<p>For example, see Seress's book [1], which includes many algorithms that upgrade standard tasks into $\mathsf{NC}$ and/or quasi-linear (sometimes Las Vegas) time, such as membership testing, computing the order, and even computing the entire composition series! The finite simple groups can be recognized in the black-box model [2] (more general/stronger than permutation groups or matrix groups), and permutational isomorphism of permutation groups of degree $n$ can be decided in $O(2^{n} |G|)$ time [3] (prior to that, the best known was the trivial $n! \cdot poly(n)$ algorithm). Many of these results were in the last 20 years, and the latter is even from 2012.</p>

<p>[1] Seress, Ákos
<a href="http://dx.doi.org/10.1017/CBO9780511546549">Permutation group algorithms</a>. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003</p>

<p>[2] Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos <a href="http://dx.doi.org/10.1515/jgth.2002.010">Black-box recognition of finite simple groups of Lie type by statistics of element orders</a>. J. Group Theory 5 (2002), no. 4, 383–401.</p>

<p>[3] László Babai, Paolo Codenotti, Youming Qiao: <a href="http://dx.doi.org/10.1007/978-3-642-31594-7_5">Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups (Extended Abstract)</a>. In: Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP'12), Springer LNCS 7391, 2012, pp. 51-62.</p>

CC BY-SA 3.0
2014-05-26T05:00:09.747Z
2014-05-26T05:00:09.747Z
Joshua Grochow
<p>I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are Schreier-Sims [1970] and Butler [1979], see e.g. 'Algorithms for Permutation groups' by Alice Niemeyer as a possible reference (?)</p>

<p>Hence, I was wondering whether there had been significant progress in the field in the last 50 years. I've seen that user NisaiVloot asked some questions about braid groups that may constitute an interesting extension of known results about permutation groups, though it's unclear to me what is the current state of research in this field as the mathematics/algorithmics communities seem somewhat out-of-sync nowadays.</p>

CC BY-SA 3.0
2014-05-24T09:40:22.650Z
A good start would probably be to see if any members of the computational group theory at http://www.cmsc.uwa.edu.au/research/cgt (Cheryl Praeger, Alice Niemeyer or Ákos Seress) have published a survey or given a talk about that recently.
Anthony Labarre
<permutations><gr.group-theory>
Recent progress in permutation groups algorithms?
Charles Mosley
# Recent progress in permutation groups algorithms?

(Asked by: username_0 on 2014-05-24)

I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are Schreier-Sims [1970] and Butler [1979], see e.g. 'Algorithms for Permutation groups' by Alice Niemeyer as a possible reference (?)

Hence, I was wondering whether there had been significant progress in the field in the last 50 years. I've seen that user NisaiVloot asked some questions about braid groups that may constitute an interesting extension of known results about permutation groups, though it's unclear to me what is the current state of research in this field as the mathematics/algorithmics communities seem somewhat out-of-sync nowadays.

**Tags:** permutations, gr.group-theory
> **Comments:**
> **username_1**: A good start would probably be to see if any members of the computational group theory at http://www.cmsc.uwa.edu.au/research/cgt (Cheryl Praeger, Alice Niemeyer or Ákos Seress) have published a survey or given a talk about that recently.  

---

## 1 answers

### Answer by username_2 on 2014-05-26. Score: 8

Certainly there has been tons of progress! (And if you really meant to ask about the last *50* years, then that includes the algorithms of Schreier-Sims and Butler that you already mentioned...)

For example, see Seress's book [1], which includes many algorithms that upgrade standard tasks into $\mathsf{NC}$ and/or quasi-linear (sometimes Las Vegas) time, such as membership testing, computing the order, and even computing the entire composition series! The finite simple groups can be recognized in the black-box model [2] (more general/stronger than permutation groups or matrix groups), and permutational isomorphism of permutation groups of degree $n$ can be decided in $O(2^{n} |G|)$ time [3] (prior to that, the best known was the trivial $n! \cdot poly(n)$ algorithm). Many of these results were in the last 20 years, and the latter is even from 2012.

[1] Seress, Ákos
[Permutation group algorithms](http://dx.doi.org/10.1017/CBO9780511546549). Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003

[2] Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos [Black-box recognition of finite simple groups of Lie type by statistics of element orders](http://dx.doi.org/10.1515/jgth.2002.010). J. Group Theory 5 (2002), no. 4, 383–401.

[3] László Babai, Paolo Codenotti, Youming Qiao: [Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups (Extended Abstract)](http://dx.doi.org/10.1007/978-3-642-31594-7_5). In: Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP'12), Springer LNCS 7391, 2012, pp. 51-62.


---

