Breaking the nlog n Barrier for Solvable-Group Isomorphism

DOI10.1137/1.9781611973105.76zbMath1422.68140arXiv1205.0642OpenAlexW2486867969MaRDI QIDQ5741784

David J. Rosenbaum

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.0642

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Finite solvable groups, theory of formations, Schunck classes, Fitting classes, (pi)-length, ranks (20D10) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Finite nilpotent groups, (p)-groups (20D15) Randomized algorithms (68W20) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (4)

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ Beating the generator-enumeration bound for \(p\)-group isomorphism ⋮ Nearly linear time isomorphism algorithms for some nonabelian group classes

This page was built for publication: Breaking the n^{log n} Barrier for Solvable-Group Isomorphism