Code equivalence and group isomorphism

Babai, L; Codenotti, P; Grochow, JA; Qiao, Y

Code equivalence and group isomorphism

Babai, L Codenotti, P Grochow, JA Qiao, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1395 - 1408
Issue Date:: 2011-05-12

Closed Access

	Filename	Description	Size
	2013005437OK.pdf	Published version	976.45 kB	Adobe PDF	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	Babai, L	en_US
dc.contributor.author	Codenotti, P	en_US
dc.contributor.author	Grochow, JA	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.date.issued	2011-05-12	en_US
dc.identifier.citation	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1395 - 1408	en_US
dc.identifier.isbn	9780898719932	en_US
dc.identifier.uri	http://hdl.handle.net/10453/32103
dc.description.abstract	The isomorphism problem for groups given by their multiplication tables has long been known to be solvable in time nlogn+O(1) decades-old quest for a polynomial-time algorithm has focused on the very difficult case of class-2 nilpotent groups (groups whose quotient by their center is abelian), with little success. In this paper we consider the opposite end of the spectrum and initiate a more hopeful program to find a polynomial-time algorithm for semisimple groups, defined as groups without abelian normal subgroups. First we prove that the isomorphism problem for this class can be solved in time n O(log log n). We then identify certain bottlenecks to polynomial-time solvability and give a polynomial-time solution to a rich subclass, namely the semisimple groups where each minimal normal subgroup has a bounded number of simple factors. We relate the results to the filtration of groups introduced by Babai and Beals (1999). One of our tools is an algorithm for equivalence of (not necessarily linear) codes in simply-exponential time in the length of the code, obtained by modifying Luks's algorithm for hypergraph isomorphism in simply-exponential time in the number of vertices (FOCS 1999). We comment on the complexity of the closely related problem of per mutational isomorphism of permutation groups.	en_US
dc.relation.ispartof	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms	en_US
dc.title	Code equivalence and group isomorphism	en_US
dc.type	Conference Proceeding
utslib.for	0802 Computation Theory and Mathematics	en_US
dc.location.activity	San Francisco, USA
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 has long been known to be solvable in time nlogn+O(1) decades-old quest for a polynomial-time algorithm has focused on the very difficult case of class-2 nilpotent groups (groups whose quotient by their center is abelian), with little success. In this paper we consider the opposite end of the spectrum and initiate a more hopeful program to find a polynomial-time algorithm for semisimple groups, defined as groups without abelian normal subgroups. First we prove that the isomorphism problem for this class can be solved in time n O(log log n). We then identify certain bottlenecks to polynomial-time solvability and give a polynomial-time solution to a rich subclass, namely the semisimple groups where each minimal normal subgroup has a bounded number of simple factors. We relate the results to the filtration of groups introduced by Babai and Beals (1999). One of our tools is an algorithm for equivalence of (not necessarily linear) codes in simply-exponential time in the length of the code, obtained by modifying Luks's algorithm for hypergraph isomorphism in simply-exponential time in the number of vertices (FOCS 1999). We comment on the complexity of the closely related problem of per mutational isomorphism of permutation groups.

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

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