Probabilistic algorithms in group theory


Conference Paper

© 1985, Springer-Verlag. 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(n3 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 Ω(n5) 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)3 expected time using nO(1) processors.

Full Text

Duke Authors

Cited Authors

  • Reif, J

Published Date

  • January 1, 1985

Published In

Volume / Issue

  • 199 LNCS /

Start / End Page

  • 341 - 350

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540156895

Digital Object Identifier (DOI)

  • 10.1007/BFb0028818

Citation Source

  • Scopus