Faster Isomorphism for ๐-Groups of Class 2 and Exponent ๐
Xiaorui Sun ยท 2023
The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order n, an algorithm with n(logn + O(1)) running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an n(1 / 4 + o(1))logn running time (Rosenbaum 2013).