Seress, Ákos Nearly linear time algorithms for permutation groups: An interplay between theory and practice. (English) Zbl 0915.20001 Acta Appl. Math. 52, No. 1-3, 183-207 (1998). This paper contains a nice survey of permutation group algorithms, concentrating on those which are polynomial time but also mentioning some which are not. The focus is on asymptotic analysis but practical implementations are mentioned also. This paper emphasizes “nearly linear time” algorithms, that is, those whose time bound is \(O(n\log^c| G|)\) for a permutation group \(G\) of degree \(n\). (In the important case of small-base groups this time bound is linear except for factors of \(\log n\).) After surveying several existing algorithms, the author presents some new nearly linear time algorithms (building on previous methods), culminating in one for finding the upper central series of a nilpotent group. This new algorithm is deterministic, unlike many other nearly linear time algorithms. Reviewer: A.J.Goodman (Rolla) Cited in 1 Review MSC: 20B40 Computational methods (permutation groups) (MSC2010) 68W10 Parallel algorithms in computer science 68W30 Symbolic computation and algebraic computation 68Q25 Analysis of algorithms and problem complexity Keywords:computational group theory; permutation groups; nearly linear time algorithms; deterministic algorithms; upper central series Software:Magma; nauty PDFBibTeX XMLCite \textit{Á. Seress}, Acta Appl. Math. 52, No. 1--3, 183--207 (1998; Zbl 0915.20001) Full Text: DOI