Algorithms for group isomorphism via group extensions and cohomology

Grochow, JA; Qiao, Y

Algorithms for group isomorphism via group extensions and cohomology

Grochow, JA Qiao, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the Annual IEEE Conference on Computational Complexity, 2014, pp. 110 - 119
Issue Date:: 2014-01-01

Closed Access

	Filename	Description	Size
	al.pdf	Published version	437.46 kB		View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Grochow, JA	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.date.issued	2014-01-01	en_US
dc.identifier.citation	Proceedings of the Annual IEEE Conference on Computational Complexity, 2014, pp. 110 - 119	en_US
dc.identifier.isbn	9781479936267	en_US
dc.identifier.issn	1093-0159	en_US
dc.identifier.uri	http://hdl.handle.net/10453/121611
dc.description.abstract	The isomorphism problem for groups given by their multiplication tables (GPI) has long been known to be solvable in nO(log n) time, but only recently has there been significant progress towards polynomial time. For example, Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. Thus, at present it is crucial to understand groups with abelian normal subgroups to develop no(log n)-time algorithms. Towards this goal we advocate a strategy via the extension theory of groups, which describes how a normal subgroup N is related to G/N via G. This strategy 'splits' GPI into two sub problems: one regarding group actions on other groups, and one regarding group co homology. The solution of these problems is essentially necessary and sufficient to solve GPI. Most previous works naturally align with this strategy, and it thus helps explain in a unified way the recent polynomial-time algorithms for other group classes. In particular, most prior results in the multiplication table model focus on the group action aspect, despite the general necessity of co homology, for example for p-groups of class 2-believed to be the hardest case of GPI. To make progress on the group co homology aspect of GPI, we consider central-radical groups, proposed in Babai et al. (SODA 2011): the class of groups such that G mod its center has no abelian normal subgroups. Recall that Babai et al. (ICALP 2012) consider the class of groups G such that G itself has no abelian normal subgroups. Following the above strategy, we solve GPI in n O(log log n) time for central-radical groups, and in polynomial time for several prominent subclasses of central-radical groups. We also solve GPI in nO(log log n)-time for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time that a nontrivial algorithm with worst-case guarantees has tackled both aspects of GPI-actions and cohomology-simultaneously. Prior to this work, only nO(log n)-time algorithms were known, even for groups with a central radical of constant size, such as Z(G) = ℤ2. To develop these algorithms we utilize several mathematical results on the detailed structure of cohomology classes, as well as algorithmic results for code equivalence, coset intersection and cyclicity testing of modules over finite-dimensional associative algebras. We also suggest several promising directions for future work. © 2014 IEEE.	en_US
dc.relation.ispartof	Proceedings of the Annual IEEE Conference on Computational Complexity	en_US
dc.relation.isbasedon	10.1109/CCC.2014.19	en_US
dc.title	Algorithms for group isomorphism via group extensions and cohomology	en_US
dc.type	Conference Proceeding
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

The isomorphism problem for groups given by their multiplication tables (GPI) has long been known to be solvable in nO(log n) time, but only recently has there been significant progress towards polynomial time. For example, Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. Thus, at present it is crucial to understand groups with abelian normal subgroups to develop no(log n)-time algorithms. Towards this goal we advocate a strategy via the extension theory of groups, which describes how a normal subgroup N is related to G/N via G. This strategy 'splits' GPI into two sub problems: one regarding group actions on other groups, and one regarding group co homology. The solution of these problems is essentially necessary and sufficient to solve GPI. Most previous works naturally align with this strategy, and it thus helps explain in a unified way the recent polynomial-time algorithms for other group classes. In particular, most prior results in the multiplication table model focus on the group action aspect, despite the general necessity of co homology, for example for p-groups of class 2-believed to be the hardest case of GPI. To make progress on the group co homology aspect of GPI, we consider central-radical groups, proposed in Babai et al. (SODA 2011): the class of groups such that G mod its center has no abelian normal subgroups. Recall that Babai et al. (ICALP 2012) consider the class of groups G such that G itself has no abelian normal subgroups. Following the above strategy, we solve GPI in n O(log log n) time for central-radical groups, and in polynomial time for several prominent subclasses of central-radical groups. We also solve GPI in nO(log log n)-time for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time that a nontrivial algorithm with worst-case guarantees has tackled both aspects of GPI-actions and cohomology-simultaneously. Prior to this work, only nO(log n)-time algorithms were known, even for groups with a central radical of constant size, such as Z(G) = ℤ2. To develop these algorithms we utilize several mathematical results on the detailed structure of cohomology classes, as well as algorithmic results for code equivalence, coset intersection and cyclicity testing of modules over finite-dimensional associative algebras. We also suggest several promising directions for future work. © 2014 IEEE.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/121611