# Faster Isomorphism for p-Groups of Class 2 and Exponent p

arXiv: https://arxiv.org/abs/2303.15412 · HTML: https://mlsanity.com/paper/2303.15412/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2023.

## Built on by (most cited first, 1 of 1)

- [Causal Learning for Heterogeneous Subgroups Based on Nonlinear Causal Kernel Clustering](https://mlsanity.com/paper/2501.11622/) (2025)

## Abstract (arXiv)

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 no(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 nO(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 individualization-refinement method and a characterization of the low rank matrix spaces.