Nearly linear time algorithms for permutation groups: An interplay between theory and practice (Q1270640)

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.