License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1830
URN: urn:nbn:de:0030-drops-18303
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1830/
Go to the corresponding LIPIcs Volume Portal

Le Gall, Francois

Efficient Isomorphism Testing for a Class of Group Extensions

pdf-format:
09001.LeGallFrancois.1830.pdf (0.2 MB)

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 $\mathbb{Z}_m$. 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.

BibTeX - Entry

@InProceedings{legall:LIPIcs:2009:1830,
  author =	{Francois Le Gall},
  title =	{{Efficient Isomorphism Testing for a Class of Group Extensions}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{625--636},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1830},
  URN =		{urn:nbn:de:0030-drops-18303},
  doi =		{10.4230/LIPIcs.STACS.2009.1830},
  annote =	{Keywords: Polynomial-time algorithms, Group isomorphism, Black-box groups}
}

Keywords: Polynomial-time algorithms, Group isomorphism, Black-box groups
Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI