Loading...
Please wait, while we are loading the content...
Similar Documents
Polynomial-time isomorphism test for groups with abelian Sylow towers (2012)
| Content Provider | CiteSeerX |
|---|---|
| Author | Babai, László Codenotti, Paolo Qiao, Youming |
| Abstract | Abstract. We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n log n 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. |
| File Format | |
| Language | English |
| Publisher Date | 2012-01-01 |
| Publisher Institution | In 29th STACS |
| Access Restriction | Open |
| Subject Keyword | Polynomial-time Isomorphism Test Abelian Sylow Tower Key New Ingredient Nontrivial Abelian Normal Subgroup Permutation Group Twisted Code Equivalence Problem Cayley Table Independent Interest Classical Code Equivalence Problem General Case Group Action Abelian Normal Subgroup Time Complexity Trivial Log Permutational Isomorphism |
| Content Type | Text |
| Resource Type | Technical Report |
