David Rosenbaum, University of Washington
Abstract
We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G and H are isomorphic. The n^(log n) barrier for group isomorphism has withstood all attacks --- even for the special cases of p-groups and solvable groups --- ever since the n^(log n + O(1)) generator-enumeration algorithm. In this work, we present the first significant improvement over n^(log n) by showing that group isomorphism is n^((1 / 2) log_p n + 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 n^(O(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.