2002/05/18 by Gene Cooperman, Cooperman, Gene
Biochemistry, Genetics and Molecular Biology · Mathematics · #DNA and Biological Computing #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #Limits and Structures in Graph Theory #Probability (math.PR) #math.GR #math.PR
paper · pdf · doi:10.48550/arxiv.math/0205203
29 pages, 6 figures, includes computational experiments
arxiv created 2002/05/18 · openalex publication_date 2002/05/18 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work presents a new, simple O(log2|G|) algorithm, the Fibonacci cube algorithm, for producing random group elements in black box groups. After the initial O(log2|G|) group operations, epsilon-uniform random elements are produced using O((log 1/epsilon)log|G|) operations each. This is the first major advance over the ten year old result of Babai [Babai91], which had required O(log5|G|) group operations. Preliminary experimental results show the Fibonacci cube algorithm to be competitive with the product replacement algorithm. The new result leads to an amusing reversal of the state of affairs for permutation group algorithms. In the past, the fastest random generation for permutation groups was achieved as an application of permutation group membership algorithms and used deep knowledge about permutation representations. The new black box random generation algorithm is also valid for permutation groups, while using no knowledge that is specific to permutation representations. As an application, we demonstrate a new algorithm for permutation group membership that is asymptotically faster than all previously known algorithms.