Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-123 | 6th September 2013 22:48

Algorithms for group isomorphism via group extensions and cohomology


Authors: Joshua Grochow, Youming Qiao
Publication: 7th September 2013 05:08
Downloads: 3530


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. Thus it is currently crucial to understand groups with abelian normal subgroups to develop n^o(log n)-time algorithms.

We advocate a strategy via the extension theory of groups, which describes how a normal subgroup N is related to G/N via G. This strategy "splits" GpI into two subproblems: one on group actions and one on group cohomology. The solution of these problems is essentially necessary and sufficient to solve GpI. Previous works naturally align with this strategy, and it thus helps explain in a unified way the recent successes on other group classes. In particular, most results in the Cayley table model focus on the group action aspect, despite the general necessity of cohomology.

To make progress on the cohomology aspect we consider central-radical groups, proposed by Babai et al. (SODA 2011): groups whose solvable normal subgroups are contained in the center. Recall that Babai et al. (ICALP 2012) considered groups with no solvable normal subgroups. Following the above strategy, we solve GpI in n^O(log log n) time for central-radical groups, and in polynomial time for several prominent subclasses of central-radical groups. We achieve the same time bounds for groups whose solvable normal subgroups are elementary abelian but not central.

Prior to our work, the easy n^O(log n) algorithm was the best known even for groups with a central radical of size 2. We use several mathematical results on the detailed structure of cohomology classes, as well as algorithms for code equivalence, coset intersection and cyclicity testing of modules over finite-dimensional algebras. We also suggest several promising directions for future work.

ISSN 1433-8092 | Imprint