NEARLY LINEAR-TIME ALGORITHMS FOR PERMUTATION-GROUPS - AN INTERPLAY BETWEEN THEORY AND PRACTICE

We survey polynomial time algorithms (both deterministic and random) f or computations with permutation groups. Particular emphasis is given to algorithms with running time of the form O(n log(C) \G\), where G i s a permutation group of degree n. In the case of small-base groups, i .e., when log \G\ is polylogarithmic as a function of n, such algorith ms run in nearly linear, O(n log(C') n) time. Important classes of gro ups, including all permutation representations of simple groups except the alternating ones, as well as most primitive groups, belong to thi s category. For large n, the majority of practical computations is car ried out on small-base groups. In the last section, we present some ne w nearly linear time algorithms, culminating in the computation of the upper central series in nilpotent groups.