Approximate representation theory of finite groups
László Babai, Karl E. Friedl · 2002
The asymptotic stability and complexity of floating point manipulation of representations of a finite group G are considered, especially splitting them into irreducible constituents and deciding their equivalence. Using rapid mixing estimates for random walks, the authors analyze a classical algorithm by J. Dixon (1970). They find that both its stability and complexity critically depend on the diameter d=diam(G,S) (S is the set that generates G). They propose a worst-case speedup by using Erdos-Renyi generators and modifying the Dixon averaging method. The overall effect in asymptotic complexity is a guaranteed (n log mod G mod )/sup O(1)/ running time.>