On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
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_ | 1866910010732183552 |
|---|---|
| author | Johnson, Dan Levet, Michael Vojtěchovský, Petr Widholm, Brett |
| author_facet | Johnson, Dan Levet, Michael Vojtěchovský, Petr Widholm, Brett |
| contents | In this paper, we investigate the computational complexity of isomorphism testing for finite groups and quasigroups, given by their multiplication tables. We crucially take advantage of their various decompositions to show the following:
- We first consider the class of groups that admit direct product decompositions, where each indecompsable factor is $O(1)$-generated, and either perfect or centerless. We show any group in this class is identified by the $O(1)$-dimensional count-free Weisfeiler--Leman (WL) algorithm with $O(\log \log n)$ rounds, and the $O(1)$-dimensional counting WL algorithm with $O(1)$ rounds. Consequently, the isomorphism problem for this class is in $\textsf{L}$. This improves upon the previous upper bound of $\textsf{TC}^{1}$, which was obtained using $O(\log n)$ rounds of the $O(1)$-dimensional counting WL (Grochow and Levet; FCT 2023, \textit{J. Comput. Syst. Sci.} 2026).
- We next consider more generally, the class of groups where each indecomposable factor is $O(1)$-generated. We exhibit an $\textsf{AC}^{3}$ canonical labeling procedure for this class. Here, we accomplish this by showing that in the multiplication table model, the direct product decomposition can be computed in $\textsf{AC}^{3}$, parallelizing the work of Kayal and Nezhmetdinov (ICALP 2009).
- Isomorphism testing between a central quasigroup $G$ and an arbitrary quasigroup $H$ is in $\textsf{NC}$. Here, we take advantage of the fact that central quasigroups admit an affine decomposition in terms of an underlying Abelian group. Only the trivial bound of $n^{\log(n)+O(1)}$-time was previously known for isomorphism testing of central quasigroups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06478 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions Johnson, Dan Levet, Michael Vojtěchovský, Petr Widholm, Brett Data Structures and Algorithms Computational Complexity Group Theory In this paper, we investigate the computational complexity of isomorphism testing for finite groups and quasigroups, given by their multiplication tables. We crucially take advantage of their various decompositions to show the following: - We first consider the class of groups that admit direct product decompositions, where each indecompsable factor is $O(1)$-generated, and either perfect or centerless. We show any group in this class is identified by the $O(1)$-dimensional count-free Weisfeiler--Leman (WL) algorithm with $O(\log \log n)$ rounds, and the $O(1)$-dimensional counting WL algorithm with $O(1)$ rounds. Consequently, the isomorphism problem for this class is in $\textsf{L}$. This improves upon the previous upper bound of $\textsf{TC}^{1}$, which was obtained using $O(\log n)$ rounds of the $O(1)$-dimensional counting WL (Grochow and Levet; FCT 2023, \textit{J. Comput. Syst. Sci.} 2026). - We next consider more generally, the class of groups where each indecomposable factor is $O(1)$-generated. We exhibit an $\textsf{AC}^{3}$ canonical labeling procedure for this class. Here, we accomplish this by showing that in the multiplication table model, the direct product decomposition can be computed in $\textsf{AC}^{3}$, parallelizing the work of Kayal and Nezhmetdinov (ICALP 2009). - Isomorphism testing between a central quasigroup $G$ and an arbitrary quasigroup $H$ is in $\textsf{NC}$. Here, we take advantage of the fact that central quasigroups admit an affine decomposition in terms of an underlying Abelian group. Only the trivial bound of $n^{\log(n)+O(1)}$-time was previously known for isomorphism testing of central quasigroups. |
| title | On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions |
| topic | Data Structures and Algorithms Computational Complexity Group Theory |
| url | https://arxiv.org/abs/2508.06478 |