2026-10-01T07:51:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26066 2026-09-23T23:59:16Z ddc:004 open_access

Parallel Algorithms for Group Isomorphism via Code Equivalence Levet, Michael Group Isomorphism Circuit Complexity Code Equivalence In this paper, we exhibit AC³ isomorphism tests for coprime extensions H ⋉ N where H is elementary Abelian and N is Abelian; and groups where Rad(G) = Z(G) is elementary Abelian and G = Soc^{*}(G). The fact that isomorphism testing for these families is in P was established respectively by Qiao, Sarma, and Tang (STACS 2011), and Grochow and Qiao (CCC 2014, SIAM J. Comput. 2017). The polynomial-time isomorphism tests for both of these families crucially leveraged small (size O(log |G|)) instances of Linear Code Equivalence (Babai, SODA 2011). Here, we combine Luks' group-theoretic method for Graph Isomorphism (FOCS 1980, J. Comput. Syst. Sci. 1982) with the fact that G is given by its multiplication table, to implement the corresponding instances of Linear Code Equivalence in AC³. As a byproduct of our work, we show that isomorphism testing of arbitrary central-radical groups is decidable using AC circuits of depth O(log³ n) and size n^{O(log log n)}. This improves upon the previous bound of n^{O(log log n)}-time due to Grochow and Qiao (ibid.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Levet 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.30 urn:nbn:de:0030-drops-260660 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode