Algorithms for Group Isomorphism via Group Extensions and Cohomology

DOI10.1137/15M1009767zbMath1475.20001arXiv1309.1776MaRDI QIDQ5283241

Youming Qiao, Joshua A. Grochow

Publication date: 21 July 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

algorithmgroup cohomologypolynomial-time algorithmgroup isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational methods for problems pertaining to group theory (20-08)

Related Items (6)

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ Filters compatible with isomorphism testing ⋮ Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing ⋮ Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice ⋮ Nearly linear time isomorphism algorithms for some nonabelian group classes

Uses Software

• GAP
• Magma
• ATLAS Group Representations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast isomorphism test for groups whose Lie algebra has genus 2
• Complexity classes of equivalence problems revisited
• Some applications of the first cohomology group
• Testing isomorphism of modules.
• Decomposing \(p\)-groups via Jordan algebras.
• Computing in general Abelian groups is hard
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On isomorphism testing of a class of 2-nilpotent groups
• Computing the order of centralizers in linear groups
• Nilpotent groups
• Construction of finite groups
• Isomorphism testing for \(p\)-groups
• The Magma algebra system. I: The user language
• Automorphism group computation and isomorphism testing in finite groups
• Some remarks on nonconnected compact Lie groups.
• An \(O(n)\) algorithm for Abelian \(p\)-group isomorphism and an \(O(n \log n)\) algorithm for Abelian group isomorphism
• The complexity of solving equations over finite groups
• Presentations of finite simple groups: profinite and cohomological approaches.
• Linear time algorithms for Abelian group isomorphism and related problems
• Cohomology theory in abstract groups. I
• Cohomology theory in abstract groups. II
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
• Existence, algorithms, and asymptotics of direct product decompositions, I
• Isomorphism in expanding families of indistinguishable groups
• Graph Isomorphism is not AC 0 reducible to Group Isomorphism
• Solvable Group Isomorphism Is (Almost) in NP ∩ coNP
• On P vs. NP and geometric complexity theory
• Generators for Simple Groups
• Finding central decompositions of p-groups
• Polynomial-Time Isomorphism Test of Groups that are Tame Extensions
• CONSTRUCTING THE GROUP PRESERVING A SYSTEM OF FORMS
• Factoring Groups Efficiently
• Is code equivalence easy to decide?
• CONSTRUCTING AUTOMORPHISM GROUPS OF p-GROUPS
• A MILLENNIUM PROJECT: CONSTRUCTING SMALL GROUPS
• Computing automorphisms of finite soluble groups
• Polynomial-time theory of matrix groups
• Algorithms for Group Isomorphism via Group Extensions and Cohomology
• Graph isomorphism in quasipolynomial time [extended abstract]
• Computing isometry groups of Hermitian maps
• Deterministic Polynomial Time Algorithms for Matrix Completion Problems
• More characteristic subgroups, Lie rings, and isomorphism tests for p-groups
• On the n^{log n} isomorphism technique (A Preliminary Report)
• Automorphisms of Finite Abelian Groups
• Breaking the n^{log n} Barrier for Solvable-Group Isomorphism
• Sur les groupes nilpotents et les anneaux de Lie

This page was built for publication: Algorithms for Group Isomorphism via Group Extensions and Cohomology