Efficient Isomorphism Testing for a Class of Group Extensions

Abstract : The group isomorphism problem asks whether two given groups are isomorphic or not. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. In this paper we study this problem for a class of groups corresponding to one of the simplest ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group A by a cyclic group Zm. We present an efficient algorithm solving the group isomorphism problem for all the groups of this class such that the order of A is coprime with m. More precisely, our algorithm runs in time almost linear in the orders of the input groups and works in the general setting where the groups are given as black-boxes.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.625-636, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00360243
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 17:01:18
Dernière modification le : mercredi 29 novembre 2017 - 10:27:37
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:39:13

Fichier

52-le_gall.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360243, version 1

Collections

Citation

François Le Gall. Efficient Isomorphism Testing for a Class of Group Extensions. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.625-636, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360243〉

Partager

Métriques

Consultations de la notice

65

Téléchargements de fichiers

100