Papers for

software engineers working on computational algebra

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Polynomial time tests for surjective maps between certain finite groups

Algorithms for Finite Group Epimorphism Testing

Abstract: 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.

Mon 7 SeptData Structures and AlgorithmsComputational Complexity

The gist

The problem studied is how to decide if you can map one finite group onto another in a way that covers every element of the second group (called a surjective homomorphism). The authors look at groups with special internal structure and develop algorithms that decide this question quickly, in time that grows reasonably with the size of the groups. These results build on previous work that could quickly test if two such groups were basically the same (isomorphic). Their methods work for several important types of groups that mathematicians often study.

Open → 2609.07429v1