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

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
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 nlognbound 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: