Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups

Publisher:
Springer
Publication Type:
Conference Proceeding
Citation:
LNCS - Automata, Languages, and Programming - Proceedings, Part I of the 39th International Colloquium on Automata, Languages and Programming, 2012, 7391 pp. 51 - 62
Issue Date:
2012-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005435OK.pdf246.51 kB
Adobe PDF
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
Please use this identifier to cite or link to this item: