Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913092355489792 |
|---|---|
| author | Levet, Michael Srivastava, Pranjal Thakkar, Dhara |
| author_facet | Levet, Michael Srivastava, Pranjal Thakkar, Dhara |
| contents | In this paper, we investigate the complexity of computing minimal faithful permutation representations for groups without abelian normal subgroups (a.k.a. Fitting-free groups). When our groups are given as quotients of permutation groups, we exhibit a polynomial-time algorithm for constructing such representations. Furthermore, in the setting of permutation groups, we obtain an $\textsf{NC}$ procedure for computing the minimal faithful permutation degree, and a randomized $\textsf{NC}$ ($\textsf{RNC}$) algorithm for computing a minimal faithful permutation representation. This improves upon the work of Das and Thakkar (STOC 2024, SIAM J. Comput. 2026), who established a Las Vegas polynomial-time algorithm for computing the minimal faithful permutation degree for this class in the setting of permutation groups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16039 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups Levet, Michael Srivastava, Pranjal Thakkar, Dhara Data Structures and Algorithms Computational Complexity Group Theory In this paper, we investigate the complexity of computing minimal faithful permutation representations for groups without abelian normal subgroups (a.k.a. Fitting-free groups). When our groups are given as quotients of permutation groups, we exhibit a polynomial-time algorithm for constructing such representations. Furthermore, in the setting of permutation groups, we obtain an $\textsf{NC}$ procedure for computing the minimal faithful permutation degree, and a randomized $\textsf{NC}$ ($\textsf{RNC}$) algorithm for computing a minimal faithful permutation representation. This improves upon the work of Das and Thakkar (STOC 2024, SIAM J. Comput. 2026), who established a Las Vegas polynomial-time algorithm for computing the minimal faithful permutation degree for this class in the setting of permutation groups. |
| title | Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups |
| topic | Data Structures and Algorithms Computational Complexity Group Theory |
| url | https://arxiv.org/abs/2501.16039 |