Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 43 min ago
PreprintarXiv licencearXiv

Algorithms for Finite Group Epimorphism Testing

  • Joshua A. Grochow
  • Pranjal Srivastava
  • Dhara Thakkar
Open at sourcePDFDOICite

Abstract

The Group Epimorphism Problem (GpEpi) asks, given two finite groups G1 and G2, whether there exists a surjective group homomorphism, or epimorphism, from G1 to G2. 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; and Groups with some constraints on their Abelian chief factors.

Related

  1. Testing epimorphism onto the bicyclic monoid is NP-complete
    Luka Carroll, Murray Elder
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. Epimorphism testing with dihedral targets
    Murray Elder, Jerry Shen, Armin Weiß
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing
    Gabriel Rioux, Joanna Marks, Riccardo Passeggeri +1
    arXivPreprintarXiv licenceFull textOptimisation & controlStatisticsarXiv
  4. Comb Tensor Network Finite-Difference Time-Domain Algorithms for 2D and 3D Electromagnetic Simulations
    Jonathan Tabares, Erika Ye, Yang Liu
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
  5. Preconditioned Hyperbolic Smoothing Modified L-BFGS Algorithms for Finite Minimax Problems
    Wenzhe Zhao
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{grochow2026algorithms,
  title = {{Algorithms for Finite Group Epimorphism Testing}},
  author = {Joshua A. Grochow and Pranjal Srivastava and Dhara Thakkar},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.07429},
  eprint = {2609.07429},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.07429},
}
RIS
TY  - UNPB
TI  - Algorithms for Finite Group Epimorphism Testing
AU  - Joshua A. Grochow
AU  - Pranjal Srivastava
AU  - Dhara Thakkar
PY  - 2026
DA  - 2026/09/07
PB  - arXiv
DO  - 10.48550/arxiv.2609.07429
UR  - https://arxiv.org/abs/2609.07429
AB  - The Group Epimorphism Problem (GpEpi) asks, given two finite groups G_1 and G_2, whether there exists a surjective group homomorphism, or epimorphism, from G_1 to G_2. 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; and Groups with some constraints on their Abelian chief factors.
ER  -