A reduction algorithm for large-base primitive permutation groups

Abstract: The authors present a nearly linear-time Las Vegas algorithm that, given a large-base primitive permutation group, constructs its natural imprimitive representation. A large-base primitive permutation group is a subgroup of a wreath product of symmetric groups S_n and S_r in product action on r-tuples of k-element subsets of {1, ..., n}, containing A_n^r. The algorithm is a randomised speed-up of a deterministic algorithm of Babai, Luks, and Seress.