We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G b H. The nlog n barrier for group isomorphism has withstood all attacks --- even for the special cases of p-groups and solvable groups --- ever since the nlog n+O(1) generator-enumeration algorithm. In this work, we present the first significant improvement over nlog n by showing that group isomorphism is n(1/2) logpn+O(1) Turing reducible to composition-series isomorphism where p is the smallest prime dividing the order of the group. Combining our reduction with an nO(p/log p) algorithm for p-group composition-series isomorphism, we obtain an n(1/2) log n+O(1) algorithm for p-group isomorphism. We then generalize our techniques from p-groups using Sylow bases to derive an n(1/2) log n+O(log n/log log n) algorithm for solvable-group isomorphism. Finally, we relate group isomorphism to the collision problem which allows us replace the 1/2 in the exponents with 1/4 using randomized algorithms and 1/6 using quantum algorithms.
['David J. Rosenbaum']
Breaking the n log n barrier for solvable-group isomorphism