Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝

The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order n, an algorithm with n (log n+O(1)) running time, attributed to Tarjan, was proposed in the 1970s [Mil78] . Despite the extensive study over the past decades, the current best group isomorphism algorithm has an n (1/4+o(1)) log n running time [Ros13] . The isomorphism testing for p-groups of (nilpotent) class 2 and exponent p has been identified as a major barrier to obtaining an n o(log n) time algorithm for the group isomorphism problem. Although the p-groups of class 2 and exponent p have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an n O(log n) running time. In this paper, we present an isomorphism testing algorithm for p-groups of class 2 and exponent p with running time n O((log n) 5/6 ) for any prime p > 2. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem [IQ19]. To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualizationrefinement method and a characterization of the low rank matrix spaces.