Fast Monte Carlo algorithms for permutation groups

DOI10.1006/jcss.1995.1024zbMath0834.20002OpenAlexW4212929410MaRDI QIDQ1892223

Gene Cooperman, Larry Finkelstein, László Babai, Eugene M. Luks, Seress, Ákos

Publication date: 4 February 1996

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1024

zbMATH Keywords

generatorspermutation groupsstrong generating setrandom subproductsfast Monte Carlo algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Probabilistic methods in group theory (20P05)

Related Items

Linear time algorithms for Abelian group isomorphism and related problems, Recognising simplicity of black-box groups by constructing involutions and their centralisers., Solvable black-box group problems are low for PP, Complexity limitations on one-turn quantum refereed games, Quantum property testing of group solvability, Unnamed Item, Black box exceptional groups of Lie type. II., Constructive membership in black-box groups, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, Constructive recognition of 𝑃𝑆𝐿(2,𝑞), Testing commutativity of a group and the power of randomization, A polynomial-time reduction algorithm for groups of semilinear or subfield class., Quantum algorithms for algebraic problems, Algorithms for matrix groups and the Tits alternative, Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules., Quantum Algorithms for a Set of Group Theoretic Problems