Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GROUP ISOMORPHISM:
Reports tagged with Group Isomorphism:
TR04-008 | 27th November 2003
Vikraman Arvind, Jacobo Toran

#### Solvable Group Isomorphism is (almost) in NP\cap coNP

The Group Isomorphism problem consists in deciding whether two input
groups \$G_1\$ and \$G_2\$ given by their multiplication tables are
isomorphic. We first give a 2-round Arthur-Merlin protocol for the
Group Non-Isomorphism problem such that on input groups \$(G_1,G_2)\$
of size \$n\$, Arthur uses ... more >>>

TR11-052 | 4th April 2011
Fabian Wagner

#### On the Complexity of Group Isomorphism

Revisions: 4 , Comments: 3

The group isomorphism problem consists in deciding whether two groups \$G\$ and \$H\$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time \$n^{\log n + O(1)}\$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

TR13-123 | 6th September 2013
Joshua Grochow, Youming Qiao

#### Algorithms for group isomorphism via group extensions and cohomology

The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>>

ISSN 1433-8092 | Imprint