Parallel Algorithms for Group Isomorphism via Code Equivalence

Michael Levet · 2026

Read Parallel Algorithms for Group Isomorphism via Code Equivalence by Michael Levet (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-13953.txt.

Introduction

Levet gives parallel AC^3 isomorphism tests for two group families. The first covers coprime extensions with elementary Abelian parts. The second covers groups whose radical equals an elementary Abelian center and that equal their iterated socle. Small instances of linear code equivalence drive both tests, implemented through Luks' graph-isomorphism method on multiplication tables. All central-radical groups get a new bound beating the old one.

Catalog record

CREATORMichael Levet
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126568
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.13953

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parallel Algorithms for Group Isomorphism via Code Equivalence Michael Levet Abstract In this paper, we exhibit AC 3 \textsf{AC}^{3} isomorphism tests for coprime extensions H ⋉ N H\ltimes N where H H is elementary Abelian and N N is Abelian; and groups where Rad ​ ( G ) = Z ​ ( G ) \text{Rad}(G)=Z(G) is elementary Abelian and G = Soc ∗ ​ ( G ) G=\text{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 | ) 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 G is given by its multiplication table, to implement the corresponding instances of Linear Code Equivalence in AC 3 \textsf{AC}^{3} . 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 3 ⁡ n ) O(\log^{3}n) and size n O ⁡ ( log ⁡ log ⁡ n ) n^{O(\log\log n)} . This improves upon the previous bound of n O ⁡ ( log ⁡ log ⁡ n ) n^{O(\log\log n)} -time due to Grochow and Qiao ( ibid .). 1 Introduction The Group Isomorphism problem ( GpI ) takes as input two finite groups G and H , and asks if there exists an isomorphism \varphi:G\to H . When the groups are given by their multiplication (Cayley) tables, it is known that GpI belongs to \textsf{NP}\cap\textsf{coAM} . The generator-enumeration strategy has time complexity n^{\log_{p}(n)+O(1)} , where n is the order of the group and p is the smallest prime dividing n . This strategy was independently discovered by Felsch and Neubüser [ FN70 ] and Tarjan (see [ Mil78 ] ). The parallel complexity of the generator-enumeration strategy has been gradually improved [ LSZ77 , Wol94 , Wag10 , CTW13 , Tan13 ] . Collins, Grochow, Levet, and Weiß recently improved the bound for the generator enumeration strategy to \exists^{\log^{2}n}\forall^{\log n}\exists^{\log n}\textsf{DTISP}(\text{polylog}(n),\log(n)), which can be simulated by depth- 4 \textsf{quasiAC}^{0} circuits of size n^{O(\log n)} [ CGLW25 ] . Algorithmically, the best known bound for GpI is n^{(1/4)\log(n)+O(1)} , due to Rosenbaum [ Ros13 ] and Luks [ Luk15 ] (see [ LGR16 , Sec. 2.2] ). Even the impressive body of work on practical algorithms for this problem in more succinct input models, led by Eick, Holt, Leedham-Green and O’Brien (e. g., [ BEO02 , ELGO02 , BE99 , CH03 ] ) still results in an n^{\Theta(\log n)} -time algorithm in the general case (see [ Wil19 , Page 2] ). In practice, such as working with computer algebra systems, the Cayley model is highly unrealistic. Instead, the groups are given by generators as permutations or matrices, or as black-boxes. In the setting of permutation groups, GpI belongs to NP [ Luk93 ] . When the groups are given by generating sets of matrices, or as black-boxes, GpI belongs to \textsf{Promise}\Sigma_{2}^{p} [ BS84 ] ; it remains open as to whether GpI belongs to NP or coNP in such succinct models. In the past several years, there have been significant advances on algorithms with worst-case guarantees on the serial runtime for special cases of this problem; we refer to [ GQ17 , DW22 , GL26 ] for a survey. Key motivation for GpI comes from its relationship to the Graph Isomorphism problem ( GI ). When the groups are given verbosely by their multiplication tables, GpI is \textsf{AC}^{0} -reducible to GI [ ZKT85 ] . On the other hand, there is no reduction from GI to GpI computable by AC circuits of depth o(\log n/\log\log n) and size n^{\text{polylog}(n)} [ CTW13 ] . In light of Babai’s breakthrough result that GI is quasipolynomial-time solvable [ Bab16 ] , GpI in the Cayley model is a key barrier to improving the complexity of GI . There is considerable evidence suggesting that GI is not NP -complete [ Sch88 , BH92 , IPZ01 , Bab16 , KST92 , AK06 ] . As verbose GpI reduces to GI , this evidence also suggests that GpI is not NP -complete. In this paper, we will investigate the parallel complexity of the Group Isomorphism problem. There are two key motivations for this. The first comes from GI , whose best known lower bound is DET [ Tor04 ] , which is a subclass of \textsf{TC}^{1} . There is a large body of work spanning almost 40 years on NC algorithms for GI – see [ LRS24 ] for a survey. In contrast, the work on NC algorithms for GpI is very new, and GpI is strictly easier than GI under \mathsf{AC^{0}} -reductions [ CTW13 ] . So it is surprising that we know more about parallelizing subclasses of GI than subclasses of GpI . The second key motivation comes from the fact that complexity-theoretic lower bounds for GpI remain open, even against depth- 2 AC circuits. In contrast, GpI is solvable using depth- 4 \mathsf{quasiAC^{0}} circuits [ CGLW25 ] . Isomorphism testing is in P for a number of families of groups, and closing the gap between P and \mathsf{AC^{0}} for special cases is a key stepping stone in trying to characterize the complexity of the general GpI problem. We now turn to stating our main results. 1.1 Isomorphism Testing of Coprime Extensions Before stating our first main theorem, we will first recall the following notation from Qiao, Sarma, and Tang [ QST11 ] . Let \mathcal{H}(\mathcal{A},\mathcal{E}) be the class of coprime extensions H\ltimes N , where N is Abelian and H is elementary Abelian. Theorem 1.1 (cf. [ QST11 ] ) . There exists a uniform \textsf{AC}^{3} algorithm that, given groups G_{1},G_{2} by their multiplication tables, decides if G_{1},G_{2}\in\mathcal{H}(\mathcal{A},\mathcal{E}) ; and if so, decides if G_{1}\cong G_{2} . There has been considerable work on polynomial-time isomorphism tests for coprime and tame extensions. Le Gall [ LG09 ] exhibited a polynomial-time isomorphism test for groups where the normal Hall subgroup N was Abelian, and the complement H was a cyclic group of order coprime to |N| . Subsequently, Qiao, Sarma, and Tang [ QST11 ] extended Le Gall’s result, exhibiting polynomial-time isomorphism tests for the cases when (i) H was O(1) -generated, and (ii) when H was an arbitrary elementary Abelian group. Babai and Qiao [ BQ12 ] subsequently gave a polynomial-time isomorphism test for the more general family of groups with Abelian Sylow towers. Grochow and Qiao [ GQ15 ] later gave a polynomial-time isomorphism test for tame extensions. The parallel complexity for isomorphism testing of coprime extensions was first investigated by Grochow and Levet [ GL26 ] , who showed that some constant-dimensional Weisfeiler–Leman algorithm identifies, in O(1) -rounds, all coprime extensions H\ltimes N , where N is Abelian and H is O(1) -generated. Consequently, they obtained that the isomorphism problem for this family belongs to L . In his thesis, Brachter [

Read the complete text