1205.0642 (David Rosenbaum)

Breaking the n^(log n) Barrier for Nilpotent-Group Isomorphism    [PDF]

David Rosenbaum

We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G \cong H. The n^(log n) barrier for group isomorphism has withstood all attacks --- even for the special cases of p-groups and nilpotent groups --- ever since 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 n^((1 / 2) log n + O(1)) algorithms for p- and nilpotent-group isomorphism. Finally, we show a new relationship between group isomorphism and the birthday problem which allows us replace the 1 / 2 in the exponents with 1 / 4 using randomized algorithms and 1 / 6 using quantum algorithms.

View original: http://arxiv.org/abs/1205.0642