Faster Isomorphism Testing of p -Groups of Frattini Class 2
SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-115-FOCS24-136
DOI: 10.1137/24m1719839 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 03.12.2025. Verfasst von Gábor Ivanyos und 4 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben. Gefördert von: Hungarian Ministry of Innovation and Technology NRDI Office, SQA/CSIRO, Australian Research Council.
Abstract (Originalsprache)
The finite group isomorphism problem asks to decide whether two finite groups of order [Formula: see text] are isomorphic. Improving the classical [Formula: see text]-time algorithm for group isomorphism is a long-standing open problem. It is generally regarded that [Formula: see text]-groups of class 2 and exponent [Formula: see text] form a bottleneck case for group isomorphism in general. The recent breakthrough by Sun [ Proceedings of the 55 th Annual ACM Symposium on Theory of Computing, 2023, pp. 433–440] presents an [Formula: see text]-time algorithm for this group class. In this paper, we improve Sun’s algorithm by presenting an [Formula: see text]-time algorithm for this group class. We also extend our result to the more general [Formula: see text]-groups of Frattini class 2 for any odd prime [Formula: see text]. Our algorithm is obtained by sharpening the key technical ingredients in Sun’s algorithm and building connections with other research topics. One intriguing connection is with the maximal and noncommutative ranks of matrix spaces, which have recently received considerable attention in algebraic complexity and computational invariant theory. Results from the theory of tensor isomorphism complexity class [J. A. Grochow and Y. Qiao, SIAM J. Comput., 52 (2023), pp. 568–617] are utilized to simplify the algorithm and to achieve the extension to [Formula: see text]-groups of Frattini class 2.
Förderung
- Hungarian Ministry of Innovation and Technology NRDI Office
- SQA/CSIRO
- Australian Research Council
- National Science Foundation
- Sydney Quantum Academy
Zitieren
APA
Ivanyos, G., Mendoza, E. J., Qiao, Y., Sun, X., & Zhang, C. (2026). Faster Isomorphism Testing of p -Groups of Frattini Class 2. SIAM Journal on Computing, 55(5), FOCS24-115-FOCS24-136. https://doi.org/10.1137/24m1719839
Vancouver
Ivanyos G, Mendoza EJ, Qiao Y, Sun X, Zhang C. Faster Isomorphism Testing of p -Groups of Frattini Class 2. SIAM Journal on Computing. 2026;55(5):FOCS24-115-FOCS24-136. doi:10.1137/24m1719839
BibTeX
@article{Ivanyos2026,
author = {Ivanyos, Gábor and Mendoza, Euan J. and Qiao, Youming and Sun, Xiaorui and Zhang, Chuanqi},
title = {Faster Isomorphism Testing of p -Groups of Frattini Class 2},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {5},
pages = {FOCS24--115--FOCS24--136},
doi = {10.1137/24m1719839}
}
EUVIMED