DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.104

Algorithms for Finite Group Epimorphism Testing

Authors: Joshua A. Grochow, Pranjal Srivastava, and Dhara Thakkar

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

The Group Epimorphism Problem (GpEpi) asks, given two finite groups G₁ and G₂, whether there exists a surjective group homomorphism, or epimorphism, from G₁ to G₂. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: - Groups with Abelian normal Hall subgroups with cyclic complement - Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement. - Groups with some constraints on their Abelian chief factors.

Cite as

Joshua A. Grochow, Pranjal Srivastava, and Dhara Thakkar. Algorithms for Finite Group Epimorphism Testing. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 104:1-104:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.ICALP.2026.104,
  author =	{Grochow, Joshua A. and Srivastava, Pranjal and Thakkar, Dhara},
  title =	{{Algorithms for Finite Group Epimorphism Testing}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{104:1--104:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.104},
  URN =		{urn:nbn:de:0030-drops-264933},
  doi =		{10.4230/LIPIcs.ICALP.2026.104},
  annote =	{Keywords: Group epimorphism problem, group-theoretic algorithms, polynomial-time algorithms, normal Hall subgroups}
}

Search Results

Documents authored by Srivastava, Pranjal

Algorithms for Finite Group Epimorphism Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message