Mathematics – Probability
Scientific paper
2002-05-18
Mathematics
Probability
29 pages, 6 figures, includes computational experiments
Scientific paper
This work presents a new, simple O(log^2|G|) algorithm, the Fibonacci cube algorithm, for producing random group elements in black box groups. After the initial O(log^2|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(log^5|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.
No associations
LandOfFree
Towards a practical, theoretically sound algorithm for random generation in finite groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Towards a practical, theoretically sound algorithm for random generation in finite groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards a practical, theoretically sound algorithm for random generation in finite groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-599024