Breaking the n^^n barrier for solvable-group isomorphism

DOI10.1137/1.9781611973105.76MaRDI QIDQ5741784zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G and H are isomorphic. The n^(log n) barrier for group isomorphism has withstood all attacks --- even for the special cases of p-groups and solvable groups --- ever since the n^(log n + O(1)) generator-enumeration algorithm. In this work, we present the first significant improvement over n^(log n) by showing that group isomorphism is n^((1 / 2) log_p n + O(1)) Turing reducible to composition-series isomorphism where p is the smallest prime dividing the order of the group. Combining our reduction with an n^(O(p / log p)) algorithm for p-group composition-series isomorphism, we obtain an n^((1 / 2) log n + O(1)) algorithm for p-group isomorphism. We then generalize our techniques from p-groups using Sylow bases to derive an n^((1 / 2) log n + O(log n / log log n)) algorithm for solvable-group isomorphism. Finally, we relate group isomorphism to the collision problem which allows us replace the 1 / 2 in the exponents with 1 / 4 using randomized algorithms and 1 / 6 using quantum algorithms.

Recommendations

• Beating the generator-enumeration bound for solvable-group isomorphism
• Beating the generator-enumeration bound for \(p\)-group isomorphism
• Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)
• An O(n) algorithm for Abelian p-group isomorphism and an O(n n) algorithm for Abelian group isomorphism
• Polynomial-time isomorphism test for groups with abelian Sylow towers.

Cited in

(12)

• Solvable black-box group problems are low for PP
• Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)
• scientific article; zbMATH DE number 1104166 (Why is no real title available?)
• Beating the generator-enumeration bound for \(p\)-group isomorphism
• Beating the generator-enumeration bound for solvable-group isomorphism
• Algorithms for group isomorphism via group extensions and cohomology
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• Nearly linear time isomorphism algorithms for some nonabelian group classes
• A systematic study of isomorphism invariants of finite groups via the Weisfeiler-Leman dimension
• On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
• On the complexity of isomorphism problems for tensors, groups, and polynomials. I: Tensor isomorphism-completeness
• Search problems in trees with symmetries: near optimal traversal strategies for individualization-refinement algorithms

This page was built for publication: Breaking the \(n^{\log^n}\) barrier for solvable-group isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741784)