Publications [#330505] of John H. Reif

Conference articles PUBLISHED

1. Reif, J, Probabilistic algorithms in group theory, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 199 LNCS (January, 1985), pp. 341-350, Springer Verlag, ISBN 9783540156895 [doi]
   (last updated on 2026/01/14)

   Abstract:
   A finite group G is commonly presented by a set of elements which generate G. We argue that for algorithmic purposes a considerably better presentation for a fixed group G is given by random generator set for G: a set of random elements which generate G. We bound the expected number of random elements requied to generate a given group G. Our main results are probabilistic algorithms which take as inputs a random generator set of a fixed permutation group G ⊆Sn. We gave O(n³ logn) expected time sequential RAM algorithms for testing membership, group inclusion and equality. Our bounds hold for any (worse case) input groups; we average only over the random generators representing the groups. Our algorithms are two orders of magnitude faster than the best previous algorithms for these group theoretic problems, which required Ω(n⁵) time even if given random generators. Furthermore, we show that in the case the input group is a 2-group with a random presentation, than those group theoretic problems can be solved by a parallel RAM in O(log n)³ expected time using n^O(1) processors.