Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2

Abstract

The finite group isomorphism problem asks whether two finite groups of order $N$ are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in time $N^{\log N + O(1)}$. Despite intensive study, the current best known algorithm has a running time of $N^{(1 / 4 + o(1))\log N}$ (Rosenbaum, '13). $p$-groups of class $2$ have been recognized as the major bottleneck for faster group isomorphism. Recent progress has led to $N^{o(\log N)}$-time algorithms for $p$-groups of class $2$ where $p$ is odd (Sun, STOC '23; Ivanyos--Mendoza--Qiao--Sun--Zhang, FOCS '24; Grochow--Qiao--Stange--Sun, STOC '25). However, the case of $p=2$, which represents the majority of $p$-groups of class 2 assuming a well-known conjecture in group enumeration, remained elusive, with essentially no progress until now. In this paper, we present an algorithm for testing the isomorphism of two 2-groups of Frattini class 2 of order $N$ in time $N^{O((\log N)^{1/2})}$. To our knowledge, this is the first $N^{o(\log N)}$-time isomorphism algorithm for a class of $2$-groups that constitutes logarithmically almost all $2$-groups, in the sense that $\lim_{N \to \infty} \frac{\log(\text{\# 2-groups of Frattini class 2 and order } \leq N)}{\log(\text{\# 2-groups of order} \leq N)} = 1$. As our main tool, we present the first non-trivial algorithms for the quadratic form space/tuple isometry problems over $\mathbb{F}_2$. These algorithms rely on combinations of combinatorial and algebraic ideas, including finite matrix group algorithms developed by Luks (FOCS '92). As far as we know, this is the first time that matrix group algorithms are used to make progress on the worst-case complexity of $p$-group isomorphism.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 3 October 2026

  Amenable groups with nearly exponential sofic profile, and quantum channels that need nearly linear memory

  Seth Douglas and Nidhal Mghirbi
• arXiv preprint · 30 September 2026

  Quantum Algorithms for Minimum Generating Set

  Bireswar Das, Udit Kumar, Kavita Samant and 1 other
• arXiv preprint · 5 October 2026

  A Cohomological Characterization of the Clifford Hierarchy

  Junaid Aftab
• arXiv preprint · 30 September 2026

  CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry

  Romie Banerjee
• arXiv preprint · 6 October 2026

  Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups

  Nader H. Bshouty

All new papers in Data Structures & Algorithms