EUVIMEDEUVIMED entdecken
Crossref

Faster Isomorphism Testing of p -Groups of Frattini Class 2

Gábor Ivanyos, Euan J. Mendoza, Youming Qiao, Xiaorui Sun, Chuanqi Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →