Polynomial-time isomorphism test for groups with no abelian normal subgroups (extended abstract)

Babai, L; Codenotti, P; Qiao, Y

Polynomial-time isomorphism test for groups with no abelian normal subgroups (extended abstract)

Babai, L Codenotti, P Qiao, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7391 LNCS (PART 1), pp. 51 - 62
Issue Date:: 2012-12-01

Closed Access

	Filename	Description	Size
	2013005435OK.pdf		246.51 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	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.date.issued	2012-12-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7391 LNCS (PART 1), pp. 51 - 62	en_US
dc.identifier.isbn	9783642315930	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28941
dc.description.abstract	We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n logn bound on the time complexity for the general case has not been improved upon over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomorphism test for groups without nontrivial abelian normal subgroups. This concludes a project started by the authors and J. A. Grochow (SODA 2011). Two key new ingredient are: (a) an algorithm to test permutational isomorphism of permutation groups in time, polynomial in the order and simply exponential in the degree; (b) the introduction of the "twisted code equivalence problem," a generalization of the classical code equivalence problem by admitting a group action on the alphabet. Both of these problems are of independent interest. © 2012 Springer-Verlag.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-642-31594-7_5	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Polynomial-time isomorphism test for groups with no abelian normal subgroups (extended abstract)	en_US
dc.type	Conference Proceeding
utslib.citation.volume	PART 1	en_US
utslib.citation.volume	7391 LNCS	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
dc.location.activity	Warwick, UK	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.issue	PART 1	en_US
pubs.publication-status	Published	en_US
pubs.volume	7391 LNCS	en_US

Abstract:

We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n logn bound on the time complexity for the general case has not been improved upon over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomorphism test for groups without nontrivial abelian normal subgroups. This concludes a project started by the authors and J. A. Grochow (SODA 2011). Two key new ingredient are: (a) an algorithm to test permutational isomorphism of permutation groups in time, polynomial in the order and simply exponential in the degree; (b) the introduction of the "twisted code equivalence problem," a generalization of the classical code equivalence problem by admitting a group action on the alphabet. Both of these problems are of independent interest. © 2012 Springer-Verlag.

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

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