2026-09-08T01:22:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26493 2026-09-05T19:45:20Z ddc:004 open_access

Algorithms for Finite Group Epimorphism Testing Grochow, Joshua A. Srivastava, Pranjal Thakkar, Dhara Group epimorphism problem group-theoretic algorithms polynomial-time algorithms normal Hall subgroups 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua A. Grochow and Pranjal Srivastava and Dhara Thakkar 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.104 urn:nbn:de:0030-drops-264933 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.104 eng https://creativecommons.org/licenses/by/4.0/legalcode