Pith. sign in

REVIEW 3 major objections 3 minor 71 references

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness

T0 review · 3 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper places Fitting-free group isomorphism in AC^3 for multiplication-table inputs, proves permutation-input versions at least as hard as graph isomorphism and linear code equivalence, and claims identification of every such group…

desk verdict Strong new AC^3 and hardness results for Fitting-free groups, but the FO section's key lemma is false; the first two theorems look solid and deserve a serious referee. read the letter →

arxiv 2504.19777 v1 pith:6LHOF37X submitted 2025-04-28 cs.CC cs.DScs.LOmath.GR

Joshua A. Grochow , Dan Johnson , Michael Levet This is my paper · ORCID
classification cs.CCcs.DScs.LOmath.GR MSC 68Q1768Q1920B4003C13
keywords groupisomorphismFitting-freegroupsAC^3circuitsparallelcomplexityWeisfeiler-Lemanfirst-orderlogiclinearcodeequivalencepermutation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that Fitting-free groups—finite groups with no nontrivial Abelian normal subgroups, the quotients left after removing the solvable radical—have a three-way complexity profile for isomorphism testing. When groups are given by multiplication tables, isomorphism is decidable in the small-depth circuit class $AC^{3}$ (unbounded fan-in gates, depth O($log^{3}$ n), polynomial size), improving the known polynomial-time bound. When the same groups are given by generating permutations, the problem becomes at least as hard as Graph Isomorphism and Linear Code Equivalence, the latter having no known subexponential-time algorithm. In addition, the paper claims every Fitting-free group of order n is identified, up to isomorphism, by a first-order formula using only O(log log n) variables, in sharp contrast to Abelian families that require O(log n) variables. These results matter because Fitting-free groups are the natural bottleneck case left after decomposing a group by its solvable radical, so the $AC^{3}$ algorithm and the FO bound are stepping stones toward the general group isomorphism problem.

What carries the argument

The load-bearing object is the permutation representation of G/PKer(G) on the non-Abelian simple factors of the socle, which has degree O(log n); here PKer(G) is the kernel of the conjugation action on those factors. The representation reduces isomorphism of Fitting-free groups to Twisted Code Equivalence, a variant of linear code equivalence in which coordinate permutations are accompanied by symbol twists from fixed groups, between codes of total length O(log n). The paper shows that the standard parallel Coset Intersection procedure, the structure-tree enumeration of small-domain transitive permutation groups, and the Twisted Code Equivalence dynamic program can all be implemented by uniform AC circuits of depth poly(log log n) with polynomial size. For the FO theorem, the mechanism is a count-free Weisfeiler–Leman pebble game, a color-refinement game that characterizes first-order logic without counting; because each non-Abelian simple factor has a generating set of seven elements with O(log n)-length words, Spoiler can pebble seven column products and O(log log n) binary-search products across the direct factors, forcing Duplicator's responses to pin down each factor and each element.

What would settle it

The FO claim would be settled by running the count-free WL Version I pebble game with O(log log n) pebbles on candidate pairs of Fitting-free groups; in particular, checking the factor-swap configuration in $G = H = A_5 \times A_5$ tests Lemma 9.12(a), since if Duplicator can survive with the swapped response, the proof of Theorem 9.1 collapses even though the theorem itself might still hold via a different argument.

Watch

Extended reading notes

Core claim

The central discovery is that the group-theoretic structure of Fitting-free groups—specifically the small permutation representation obtained by letting G act on the non-Abelian simple factors of its socle and factoring out the kernel PKer(G)—converts the isomorphism problem into an instance of Twisted Code Equivalence of total length O(log n). Starting from the multiplication table, the paper implements each subroutine of the previous polynomial-time algorithm, including the standard parallel Coset Intersection procedure and the structure-tree machinery, with AC circuits of depth poly(log log n), and it solves the resulting code-equivalence instance in additional depth O($log^{2}$ n · poly(log log n)). The matching hardness direction embeds any binary linear code C into a group G_C = $π^{{-1}}$(C) inside a wreath product of alternating groups, so that code equivalence becomes group isomorphism; because this embedding is $AC^{0}$-computable and the group is Fitting-free, Graph Isomorphism and Linear Code Equivalence reduce to the permutation-generator version. The descriptive-complexity result asserts that O(log log n) variables suffice in first-order logic without counting, by pebbling seven short-word generators per simple factor and using a binary-search strategy on the number of socle factors to force Duplicator to match factors and then elements.

Load-bearing premise

The FO-identification theorem rests on Lemma 9.12(a), which asserts that a Duplicator response that places a socle element in the wrong direct factor can be punished by Spoiler in O(1) extra pebbles and O(log log n) extra rounds; if that factor-isolation guarantee fails, the O(log log n) variable bound does not follow from the submitted proof.

Editorial extensions

If this is right

  • If Theorem 1.1 is right, Fitting-free group isomorphism in the multiplication-table model moves from polynomial time down to AC^3, giving one of the strongest known parallel upper bounds for a class that is a bottleneck for general group isomorphism.
  • Because Lemma 7.11 decides Fitting-freeness in AC^0, the same circuit family can both certify membership in the class and solve isomorphism for all inputs.
  • The AC^0 reduction from Linear Code Equivalence means a polynomial-time algorithm for Fitting-free permutation-group isomorphism would imply the same for Linear Code Equivalence; in particular, the practical permutation-group approach cannot have a polynomial worst case unless code equivalence does.
  • The O(log log n)-variable FO identification directly contrasts with infinite families of Abelian groups that require O(log n) variables, so variable count separates these two natural classes.
  • Corollary 9.4 gives an ∃^{log n log log n} FOLL decision procedure for isomorphism between a Fitting-free group and an arbitrary group, simulated by quasiFOLL circuits of size n^{O(log log n)}.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the FO proof is repaired, the same binary-search pebbling strategy may identify any group whose socle is a direct product of non-Abelian simple groups even when the group is not itself Fitting-free, because the argument never uses the quotient beyond the unique-extension lemma.
  • The AC^3 algorithm's depth is dominated by the Twisted Code Equivalence solver; replacing that subroutine by a group-theoretic normalizer computation could plausibly lower the bound toward AC^1 or L, which the paper leaves open.
  • The hardness construction produces groups of order about 240^n from codes of length n, so the right parameter for the permutation-group problem may be the number of simple factors rather than the order; testing isomorphism of Fitting-free groups with few simple factors might still be tractable.
  • A natural testable extension is to check whether the O(log log n) variable bound holds for count-free WL Version II as well as Version I, since the paper's remark on the socle being O(log log n)-generated suggests a generator-socle route that may generalize.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies the complexity of isomorphism testing for Fitting-free groups. In the Cayley-table model, the authors give a uniform AC^3 algorithm (depth O(log^2 n * poly(log log n)) and size poly(n)) that decides Fitting-freeness and isomorphism, generalizing the polynomial-time algorithm of Babai, Codenotti, and Qiao. In the permutation-generator model, they show that Linear Code Equivalence and Graph Isomorphism are polynomial-time reducible to isomorphism testing of Fitting-free permutation groups. Finally, the paper claims that every Fitting-free group of order n is identified by a first-order formula without counting that uses O(log log n) variables, strengthening a prior result of Brachter that used counting. The first two results appear to be supported by the submitted arguments, but the FO identification claim rests on a false lemma (Lemma 9.12(a)) and is not established as written.

Significance. If the parallel and hardness results are correct, they are significant: the AC^3 upper bound is a substantial improvement over the previous polynomial-time bound for Fitting-free groups in the Cayley model, and the reduction from Linear Code Equivalence to isomorphism of Fitting-free permutation groups is a strong new lower-bound result. The claimed FO identification theorem would also be a noteworthy strengthening of Brachter's counting-WL result, but the proof currently contains a false lemma and the theorem is therefore unsupported. The manuscript also contains useful technical contributions, including a careful depth analysis of Luks's Coset Intersection algorithm for small domains and a parallel treatment of the reduction to Twisted Code Equivalence.

major comments (3)
  1. [Section 9.2, Lemma 9.12(a)] Lemma 9.12(a) is false. Take G = H = A5 × A5, so k = 2 and ℓ = 1. Let π be the automorphism swapping the two factors. Suppose Spoiler first pebbles x_1,...,x_7 and p_1 according to Definition 9.10, and Duplicator answers with x'_j = π(x_j) and p'_1 = π(p_1). Because π is an automorphism, all weight hypotheses of Lemma 9.12 hold. Now Spoiler pebbles g ∈ S_1; Duplicator responds with h = π(g) ∈ S'_2, which satisfies condition (a) with a ≠ b. Nevertheless, Duplicator can continue to respond with π to every subsequent pebble, keeping the entire partial map a restriction of an isomorphism, so Spoiler cannot force a win. The proof of Case 1 fails because for this π, wt(p_1 · s_{1,1}^{-1}) = wt(p'_1 · (h'_1)^{-1}), so Lemma 9.11 gives no contradiction; Case 3 fails because h and h'_1 both lie in S'_2, so their product has weight 1, not 2 as the proof assumes. Since Lemma 9.12 is the step that forces Duplicator's factor-wise alignment, the derivations of Theorem 9.2, Theorem 9.1, and Corollary 9.4 are unsupported as written.
  2. [Section 9.1, footnote 5] Footnote 5 states that [CL24, Lemma 6.10], which assumes h ∉ Soc(H), can be extended to the case wt(h) > 1, citing that the proof shows the stronger statement. This is an unproved extension of a prior result and is used in Lemma 9.9 and in the proof of Theorem 9.2. The claim is plausible but needs a proof; as written, it is an additional gap in the FO section, even though the falsity of Lemma 9.12(a) already breaks the argument.
  3. [Section 9.2, proof of Theorem 9.2] The proof of Theorem 9.2 uses Lemma 9.12 to conclude that Duplicator's responses to the seven generators of each simple factor must lie in the corresponding factor and must induce an isomorphism S_i ≅ S'_i. Because Lemma 9.12(a) is false, this conclusion is not justified, and the final argument that the induced isomorphism of the socle extends to G → H collapses. Remark 9.13 outlines an alternative route via O(log log n)-generation of the socle, but that route is not developed into a proof and the remark explicitly leaves open whether count-free WL can achieve the stated bounds; it therefore does not repair the submitted proof.
minor comments (3)
  1. [Definition 9.10] The notation x_i is used in the definition of p_1 (e.g., p_1 := ∏_{i=1}^{k/2} x_i), but x_i is never defined; only x_{i,j} and x_j are introduced. Please clarify the intended meaning of x_i.
  2. [Theorem 6.13] The bound |PISO(G,H)| ≤ |G|·c^{2m} refers to an unspecified constant c; the proof should state explicitly that c is an absolute constant.
  3. [Abstract] The abstract contains the typo 'Nor mal' in 'Abelian Nor mal Subgroups'; it should be 'normal'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation found: the FO section has a correctness gap (Lemma 9.12(a)) but not a circular step.

full rationale

Walking the derivation chain: Theorem 1.1 reduces Fitting-free isomorphism in the Cayley-table model to Twisted Code Equivalence on small-domain instances, using Luks's coset-intersection procedure, the BLS87 permutation-group toolkit, and the BCQ12/Cod11 reduction apparatus; these are externally published algorithms and structural results, and no parameter is fitted to any output of the theorem. The hardness result Theorem 8.1 is a direct code-to-group construction whose correctness proof is a standard reduction, and its use of [BCGQ11, Lemma 2.1] is an independent structural fact about direct products of simple groups, not a renamed version of the target statement. The FO section (Theorems 9.1/9.2) relies heavily on same-author results [CL24, GL23a, GL23b] and on a new Lemma 9.12(a), but reliance on prior published lemmas is not circular because their statements are not the theorem being proved and they carry independent proofs. The serious problem in that section is correctness, not circularity: Lemma 9.12(a) is unsupported and, as the surrounding analysis notes, appears refuted by the factor-swapping automorphism of A5 x A5, so the proof of Theorem 9.2 is not established as written. That is an unproven or false lemma (and Remark 9.13 itself suggests an alternative route), but it does not make the O(log log n) variable bound equal to an input by construction, nor does any equation in the paper equate a derived quantity with its own input. No fitted-input-called-prediction, self-definitional reduction, or author-imported-uniqueness pattern is present.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper introduces no free parameters or invented entities. Its claims rest on a large body of cited theorems and prior co-authored lemmas; the most fragile imported premises are the unproven extension of [CL24, Lemma 6.10] and the correctness of Luks's and Codenotti's algorithms as black boxes.

assumptions (8)
  • standard math Finite simple groups are 2-generated and satisfy the Babai-Kantor-Lubotsky 7-generator bound with word length C log |S| (Theorem 9.3)
    Used in Section 9, Definition 9.10 and Theorem 9.2, to pebble generators of the simple factors of the socle.
  • standard math Cameron's bound: primitive permutation groups other than S_m and A_m have order at most m^{sqrt(m)} (Theorem 6.4)
    Used in Lemma 6.5 and Lemma 6.6 to bound |G| and |PAut(G)| by poly(n) when the degree m is O(log n).
  • domain assumption Luks's Coset Intersection algorithm and Problem I/II recursion are correct (Luk99, Props 3.1 and 6.1)
    Proposition 3.3 imports the recursive decomposition of Problem II from [Luk99] without re-deriving correctness; only the depth and size are re-analyzed.
  • domain assumption Codenotti's dynamic-programming algorithm for Twisted Code Equivalence is correct (Cod11, Thm 4.2.1)
    Theorem 4.3 only re-analyzes depth and size; correctness is inherited from Codenotti's thesis as a black box.
  • domain assumption BCQ12 structural lemmas: extension of socle isomorphisms (Lemma 7.6), diagonal-respecting isomorphism decomposition (Corollary 7.7 and Equation 1), and permutational isomorphisms of G/PKer determine ISOds (Lemma 7.9)
    Used in Sections 7.1 through 7.4; these come from [BCGQ11, BCQ12, Cod11] and are not re-proved.
  • ad hoc to paper Unproved extension of [CL24, Lemma 6.10] from h not in Soc(H) to wt(h) > 1 (footnote 5)
    Lemma 9.8 relies on this extension; the paper does not reproduce the proof. It is load-bearing for the weight-based pebbling argument in Theorem 9.2.
  • domain assumption Grochow-Levet witness theorem: if G is Fitting-free, H is not isomorphic to G, and phi is an isomorphism of socles that does not extend, there exists g and a weight-one s_gh witnessing the failure (GL23a, Theorem 4.17)
    Used in the final paragraph of Theorem 9.2's proof to find the distinguishing conjugation mismatch.
  • domain assumption BLS87 parallel permutation group toolbox (order, membership, kernels, pointwise stabilizers, Schreier generators, and related problems) is in NC (Lemma 2.2)
    The whole AC^3 result assumes these subroutines are correct and parallelizable at the stated depth and size.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness." pith.science (2026). https://pith.science/paper/6LHOF37X

@misc{pith2026250419777,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6LHOF37X}},
  note         = {Machine review of arXiv:2504.19777}
}
abstract

In this paper, we exhibit an $\textsf{AC}^{3}$ isomorphism test for groups without Abelian normal subgroups (a.k.a. Fitting-free groups), a class for which isomorphism testing was previously known to be in $\mathsf{P}$ (Babai, Codenotti, and Qiao; ICALP '12). Here, we leverage the fact that $G/\text{PKer}(G)$ can be viewed as permutation group of degree $O(\log |G|)$. As $G$ is given by its multiplication table, we are able to implement the solution for the corresponding instance of Twisted Code Equivalence in $\textsf{AC}^{3}$. In sharp contrast, we show that when our groups are specified by a generating set of permutations, isomorphism testing of Fitting-free groups is at least as hard as Graph Isomorphism and Linear Code Equivalence (the latter being $\textsf{GI}$-hard and having no known subexponential-time algorithm). Lastly, we show that any Fitting-free group of order $n$ is identified by $\textsf{FO}$ formulas (without counting) using only $O(\log \log n)$ variables. This is in contrast to the fact that there are infinite families of Abelian groups that are not identified by $\textsf{FO}$ formulas with $o(\log n)$ variables (Grochow & Levet, FCT '23).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 36 canonical work pages

  1. [1]

    Arvind and Piyush P

    V. Arvind and Piyush P. Kurur. Graph isomorphism is in SPP . Information and Computation , 204(5):835--852, 2006. https://doi.org/10.1016/j.ic.2006.02.002 doi:10.1016/j.ic.2006.02.002

    doi:10.1016/j.ic.2006.02.002 2006

  2. [2]

    Graph isomorphism in quasipolynomial time [extended abstract]

    L\' a szl\' o Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In S TOC '16--- P roceedings of the 48th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 684--697. ACM, New York, 2016. Preprint of full version at arXiv:1512.03547v2 [cs.DS] . https://doi.org/10.1145/2897518.2897542 doi:10.1145/2897518.2897542

    arXiv 2016

  3. [3]

    Asymptotic improvements to provable algorithms for the code equivalence problem

    Huck Bennett, Drisana Bhatia, Jean-François Biasse, Medha Durisheti, Lucas LaBuff, Vincenzo Pallozzi Lavorante, and Philip Waitkevich. Asymptotic improvements to provable algorithms for the code equivalence problem. Cryptology ePrint Archive, Paper 2025/187, 2025. To appear, ISIT '25. URL: https://eprint.iacr.org/2025/187

    work page 2025

  4. [4]

    Grochow, and Youming Qiao

    L \'a szl \'o Babai, Paolo Codenotti, Joshua A. Grochow, and Youming Qiao. Code equivalence and group isomorphism. In Proceedings of the Twenty-Second Annual ACM--SIAM Symposium on Discrete Algorithms ( SODA11 ) , pages 1395--1408, Philadelphia, PA, 2011. SIAM. https://doi.org/10.1137/1.9781611973082.107 doi:10.1137/1.9781611973082.107

    doi:10.1137/1.9781611973082.107 2011

  5. [5]

    Polynomial-time isomorphism test for groups with no abelian normal subgroups - (extended abstract)

    L \'a szl \'o Babai, Paolo Codenotti, and Youming Qiao. Polynomial-time isomorphism test for groups with no abelian normal subgroups - (extended abstract). In International Colloquium on Automata, Languages, and Programming (ICALP) , pages 51--62, 2012. https://doi.org/10.1007/978-3-642-31594-7_5 doi:10.1007/978-3-642-31594-7_5

    work page doi:10.1007/978-3-642-31594-7_5 2012

  6. [6]

    Construction of finite groups

    Hans Ulrich Besche and Bettina Eick. Construction of finite groups. J. Symb. Comput. , 27(4):387--404, 1999. https://doi.org/10.1006/jsco.1998.0258 doi:10.1006/jsco.1998.0258

    arXiv 1999

  7. [7]

    Hans Ulrich Besche, Bettina Eick, and E.A. O'Brien. A millennium project: Constructing small groups. Intern. J. Alg. and Comput , 12:623--644, 2002. https://doi.org/10.1142/S0218196702001115 doi:10.1142/S0218196702001115

    doi:10.1142/s0218196702001115 2002

  8. [8]

    Superpolynomial circuits, almost sparse oracles and the exponential hierarchy

    Harry Buhrman and Steven Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In R. K. Shyamasundar, editor, Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings , volume 652 of Lecture Notes in Computer Science , pages 116--127. Springer,...

    doi:10.1007/3-540-56287-7 1992

Show all 71 references
  1. [9]

    Babai, W.M

    L. Babai, W.M. Kantor, and A. Lubotsky. Small-diameter cayley graphs for finite simple groups. European Journal of Combinatorics , 10(6):507--522, 1989. https://doi.org/10.1016/S0195-6698(89)80067-8 doi:10.1016/S0195-6698(89)80067-8

    1989 doi

  2. [10]

    Mix Barrington, Peter Kadau, Klaus - J \" o rn Lange, and Pierre McKenzie

    David A. Mix Barrington, Peter Kadau, Klaus - J \" o rn Lange, and Pierre McKenzie. On the complexity of some problems on groups input as multiplication tables. J. Comput. Syst. Sci. , 63(2):186--200, 2001. https://doi.org/10.1006/jcss.2001.1764 doi:10.1006/jcss.2001.1764

    2001

  3. [11]

    Babai, E

    L. Babai, E. Luks, and A. Seress. Permutation groups in NC . In STOC 1987 , STOC '87, pages 409--420, New York, NY, USA, 1987. Association for Computing Machinery. https://doi.org/10.1145/28395.28439 doi:10.1145/28395.28439

    1987

  4. [12]

    Brooksbank, Joshua Maglione, and James B

    Peter A. Brooksbank, Joshua Maglione, and James B. Wilson. A fast isomorphism test for groups whose Lie algebra has genus 2. Journal of Algebra , 473:545--590, 2017. https://doi.org/10.1016/j.jalgebra.2016.12.007 doi:10.1016/j.jalgebra.2016.12.007

    2017 doi

  5. [13]

    Polynomial-time isomorphism test for groups with Abelian Sylow towers

    L\'aszl\'o Babai and Youming Qiao. Polynomial-time isomorphism test for groups with Abelian Sylow towers. In 29th STACS , pages 453 -- 464. Springer LNCS 6651, 2012. https://doi.org/10.4230/LIPIcs.STACS.2012.453 doi:10.4230/LIPIcs.STACS.2012.453

    2012 doi

  6. [14]

    Combinatorial approaches to the group isomorphism problem

    Jendrik Brachter. Combinatorial approaches to the group isomorphism problem . PhD thesis, TU Darmstadt, Sept. 2023. URL: https://tuprints.ulb.tu-darmstadt.de/26387/1/thesis_brachter.pdf

    2023

  7. [15]

    On the complexity of matrix group problems I

    L \' a szl \' o Babai and Endre Szemer \' e di. On the complexity of matrix group problems I . In 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984 , pages 229--240. IEEE Computer Society, 1984. https://doi.org/10.1109/...

    1984

  8. [16]

    On the Weisfeiler--Leman dimension of finite groups

    Jendrik Brachter and Pascal Schweitzer. On the Weisfeiler--Leman dimension of finite groups. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbr \" u cken, Germany, July 8-11,...

    2020

  9. [17]

    Finite permutation groups and finite simple groups

    Peter Cameron. Finite permutation groups and finite simple groups. Bulletin of The London Mathematical Society - BULL LOND MATH SOC , 13:1--22, 01 1981. https://doi.org/10.1112/blms/13.1.1 doi:10.1112/blms/13.1.1

    1981 doi

  10. [18]

    An optimal lower bound on the number of variables for graph identification

    Jin-Yi Cai, Martin F\" u rer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica , 12(4):389--410, 1992. Originally appeared in SFCS '89. https://doi.org/10.1007/BF01305232 doi:10.1007/BF01305232

    1992 doi

  11. [19]

    Collins, Joshua A

    Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, and Armin Wei . Constant depth circuit complexity for generating quasigroups. In Jonathan D. Hauenstein, Wen - shin Lee, and Shaoshi Chen, editors, Proceedings of the 2024 International Symposium on Symbolic and Algebraic...

    2024 arXiv

  12. [20]

    Cannon and Derek F

    John J. Cannon and Derek F. Holt. Automorphism group computation and isomorphism testing in finite groups. J. Symb. Comput. , 35:241--267, March 2003. https://doi.org/10.1016/S0747-7171(02)00133-5 doi:10.1016/S0747-7171(02)00133-5

    2003 doi

  13. [21]

    Collins and Michael Levet

    Nathaniel A. Collins and Michael Levet. Count-free Weisfeiler–Leman and group isomorphism. International Journal of Algebra and Computation , 34(03):283--330, 2024. https://doi.org/10.1142/S0218196724500103 doi:10.1142/S0218196724500103

    2024 doi

  14. [22]

    Problems complete for deterministic logarithmic space

    Stephen A Cook and Pierre McKenzie. Problems complete for deterministic logarithmic space. Journal of Algorithms , 8(3):385--394, 1987. https://doi.org/10.1016/0196-6774(87)90018-6 doi:10.1016/0196-6774(87)90018-6

    1987 doi

  15. [23]

    Testing Isomorphism of Combinatorial and Algebraic Structures

    Paolo Codenotti. Testing Isomorphism of Combinatorial and Algebraic Structures . PhD thesis, University of Chicago , 2011. URL: https://people.cs.uchicago.edu/ laci/students/codenotti.pdf

    2011

  16. [24]

    Nathaniel A. Collins. Weisfeiler–Leman and group isomorphism, 2023. Undergraduate Thesis. University of Coloardo Boulder. URL: https://scholar.colorado.edu/concern/undergraduate_honors_theses/6m311q80b

    2023

  17. [25]

    Graph isomorphism is not AC^0 -reducible to group isomorphism

    Arkadev Chattopadhyay, Jacobo Tor\' a n, and Fabian Wagner. Graph isomorphism is not AC^0 -reducible to group isomorphism. ACM Trans. Comput. Theory , 5(4):Art. 13, 13, 2013. Preliminary version appeared in FSTTCS '10; ECCC Tech. Report TR10-117. https://doi.org/10.1145/254008...

    2013 doi

  18. [26]

    Dixon and Brian Mortimer

    John D. Dixon and Brian Mortimer. Permutation groups , volume 163 of Graduate Texts in Mathematics . Springer-Verlag, New York, 1996. https://doi.org/10.1007/978-1-4612-0731-3 doi:10.1007/978-1-4612-0731-3

    1996 doi

  19. [27]

    The minimal faithful permutation degree of groups without abelian normal subgroups

    Bireswar Das and Dhara Thakkar. The minimal faithful permutation degree of groups without abelian normal subgroups. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 118–129, New York, NY, USA, 2024. Association for Computing Machinery. h...

    2024

  20. [28]

    Heiko Dietrich and James B. Wilson. Group isomorphism is nearly-linear time for most orders. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 457--467, 2022. https://doi.org/10.1109/FOCS52979.2021.00053 doi:10.1109/FOCS52979.2021.00053

    2021

  21. [29]

    Embedding and canonizing graphs of bounded genus in logspace

    Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , STOC '14, page 383–392, New York, NY, USA, 2014. Association for Computing Machinery. htt...

    2014

  22. [30]

    Bettina Eick, C. R. Leedham-Green, and E. A. O'Brien. Constructing automorphism groups of p -groups. Comm. Algebra , 30(5):2271--2295, 2002. https://doi.org/10.1081/AGB-120003468 doi:10.1081/AGB-120003468

    2002 doi

  23. [31]

    Canonizing graphs of bounded tree width in logspace

    Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. ACM Trans. Comput. Theory , 9(3), Oct. 2017. https://doi.org/10.1145/3132720 doi:10.1145/3132720

    2017 doi

  24. [32]

    Felsch and J

    V. Felsch and J. Neub\" u ser. On a programme for the determination of the automorphism group of a finite group. In Computational P roblems in A bstract A lgebra ( P roc. C onf., O xford, 1967) , pages 59--60. 1970

    1967

  25. [33]

    Furst, James B

    Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory , 17(1):13--27, 1984. https://doi.org/10.1007/BF01744431 doi:10.1007/BF01744431

    1984 doi

  26. [34]

    Grochow and Michael Levet

    Joshua A. Grochow and Michael Levet. On the descriptive complexity of groups without abelian normal subgroups (extended abstract). In Antonis Achilleos and Dario Della Monica, editors, Proceedings of the Fourteenth International Symposium on Games, Automata, Logics, and Formal...

    2023

  27. [35]

    Grochow and Michael Levet

    Joshua A. Grochow and Michael Levet. On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman . In Henning Fernau and Klaus Jansen, editors, Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedi...

    2023 arXiv

  28. [36]

    Grochow and Youming Qiao

    Joshua A. Grochow and Youming Qiao. Polynomial-time isomorphism test of groups that are tame extensions - (extended abstract). In Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings , pages 578--589, 2015. http...

    2015 doi

  29. [37]

    Grochow and Youming Qiao

    Joshua A. Grochow and Youming Qiao. Algorithms for group isomorphism via group extensions and cohomology. SIAM J. Comput. , 46(4):1153--1216, 2017. Preliminary version in IEEE Conference on Computational Complexity (CCC) 2014 (DOI:10.1109/CCC.2014.19). Also available as arXiv:...

    2017 arXiv

  30. [38]

    Grochow and Youming Qiao

    Joshua A. Grochow and Youming Qiao. On p-group isomorphism: Search-to-decision, counting-to-decision, and nilpotency class reductions via tensors. ACM Trans. Comput. Theory , 16(1):2:1--2:39, 2024. Extended abstract at CCC '21 doi:10.4230/LIPIcs.CCC.2021.16; preliminary versio...

    2024 arXiv

  31. [39]

    Testing graph isomorphism in parallel by playing a game

    Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14,...

    2006 doi

  32. [40]

    Definability hierarchies of generalized quantifiers

    Lauri Hella. Definability hierarchies of generalized quantifiers. Annals of Pure and Applied Logic , 43(3):235 -- 271, 1989. https://doi.org/10.1016/0168-0072(89)90070-5 doi:10.1016/0168-0072(89)90070-5

    1989 doi

  33. [41]

    Logical hierarchies in PTIME

    Lauri Hella. Logical hierarchies in PTIME . Information and Computation , 129(1):1--19, 1996. https://doi.org/10.1006/inco.1996.0070 doi:10.1006/inco.1996.0070

    1996

  34. [42]

    D. Holt, B. Eick, and E. O'Brien. Handbook of Computational Group Theory . Chapman and Hall/CRC, 2005

    2005

  35. [43]

    Describing graphs: A first-order approach to graph canonization

    Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988 , pages 59--81. Springer New York, New...

    1988 doi

  36. [44]

    Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512--530, 2001

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512--530, 2001. https://doi.org/10.1006/jcss.2001.1774 doi:10.1006/jcss.2001.1774

    2001

  37. [45]

    Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing

    G \' a bor Ivanyos and Youming Qiao. Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. SIAM J. Comput. , 48(3):926--963, 2019. https://doi.org/10.1137/18M1165682 doi:10.1137...

    2019 doi

  38. [46]

    o bler, Uwe Sch \

    Johannes K \" o bler, Uwe Sch \" o ning, and Jacobo Tor \' a n. Graph isomorphism is low for PP . Comput. Complex. , 2:301--330, 1992. https://doi.org/10.1007/BF01200427 doi:10.1007/BF01200427

    1992 doi

  39. [47]

    Rosenbaum

    Fran c ois Le Gall and David J. Rosenbaum. On the group and color isomorphism problems. arXiv:1609.08253 [cs.CC] , 2016

    2016 arXiv

  40. [48]

    Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman

    Michael Levet, Puck Rombach, and Nicholas Sieger. Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman . In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) , volume 294 of Leibniz International Proceedin...

    2024 doi

  41. [49]

    R. J. Lipton, L. Snyder, and Y. Zalcstein. The complexity of word and isomorphism problems for finite groups. Yale University Dept. of Computer Science Research Report \# 91, 1977. URL: https://apps.dtic.mil/dtic/tr/fulltext/u2/a053246.pdf

    1977

  42. [50]

    Eugene M. Luks. Parallel algorithms for permutation groups and graph isomorphism. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986 , pages 292--302. IEEE Computer Society, 1986. https://doi.org/10.1109/SFCS.1986.39 doi:10.1109/SF...

    1986 doi

  43. [51]

    Permutation groups and polynomial-time computation

    Eugene Luks. Permutation groups and polynomial-time computation. DIMACS Series in Discrete Mathematics and Theoretical Computer Science , 11, 09 1993. https://doi.org/10.1090/dimacs/011/11 doi:10.1090/dimacs/011/11

    1993 doi

  44. [52]

    Eugene M. Luks. Hypergraph isomorphism and structural equivalence of boolean functions. In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georg...

    1999

  45. [53]

    Eugene M. Luks. Group isomorphism with fixed subnormal chains, 2015. https://arxiv.org/abs/1511.00151 arXiv:1511.00151

    2015 arXiv

  46. [54]

    Lewis and James B

    Mark L. Lewis and James B. Wilson. Isomorphism in expanding families of indistinguishable groups. 4(1):73--110, 2012. https://doi.org/doi:10.1515/gcc-2012-0008 doi:doi:10.1515/gcc-2012-0008

    2012 doi

  47. [55]

    Gary L. Miller. On the n^ n isomorphism technique (a preliminary report). In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , STOC '78, pages 51--58, New York, NY, USA, 1978. Association for Computing Machinery. https://doi.org/10.1145/800133.804331 doi:1...

    1978

  48. [56]

    Message to sci.math.research google group

    Takunari Miyazaki. Message to sci.math.research google group. https://groups.google.com/g/sci.math.research/c/puZxGj9HXKI/m/CeyH2yyyNFUJ https://groups.google.com/g/sci.math.research/c/puZxGj9HXKI/m/CeyH2yyyNFUJ, 1996

    1996

  49. [57]

    Petrank and R.M

    E. Petrank and R.M. Roth. Is code equivalence easy to decide? IEEE Transactions on Information Theory , 43(5):1602--1604, 1997. https://doi.org/10.1109/18.623157 doi:10.1109/18.623157

    1997 doi

  50. [58]

    Youming Qiao, Jayalal M. N. Sarma, and Bangsheng Tang. On isomorphism testing of groups with normal Hall subgroups. In Proc. 28th STACS , pages 567--578, 2011. https://doi.org/10.4230/LIPIcs.STACS.2011.567 doi:10.4230/LIPIcs.STACS.2011.567

    2011 doi

  51. [59]

    Rosenbaum

    David J. Rosenbaum. Bidirectional collision detection and faster deterministic isomorphism testing. arXiv:1304.3935 [cs.DS] , 2013

    2013 arXiv

  52. [60]

    Graph isomorphism is in the low hierarchy

    Uwe Sch \" o ning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences , 37(3):312 -- 323, 1988. https://doi.org/10.1016/0022-0000(88)90010-4 doi:10.1016/0022-0000(88)90010-4

    1988 doi

  53. [61]

    Permutation group algorithms , volume 152 of Cambridge Tracts in Mathematics

    \'Akos Seress. Permutation group algorithms , volume 152 of Cambridge Tracts in Mathematics . Cambridge University Press, Cambridge, 2003. https://doi.org/10.1017/CBO9780511546549 doi:10.1017/CBO9780511546549

    2003 doi

  54. [62]

    Borel sets and circuit complexity

    Michael Sipser. Borel sets and circuit complexity. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual A...

    1983

  55. [63]

    Towards Understanding Satisfiability, Group Isomorphism and Their Connections

    Bangsheng Tang. Towards Understanding Satisfiability, Group Isomorphism and Their Connections . PhD thesis, Tsinghua University, 2013. URL: http://papakonstantinou.org/periklis/pdfs/bangsheng_thesis.pdf

    2013

  56. [64]

    Maximal subgroups of direct products

    Jacques Th \' e venaz. Maximal subgroups of direct products. Journal of Algebra , 198(2):352--361, 1997. https://doi.org/10.1006/jabr.1997.7095 doi:10.1006/jabr.1997.7095

    1997

  57. [65]

    On the hardness of graph isomorphism

    Jacobo Tor \' a n. On the hardness of graph isomorphism. SIAM J. Comput. , 33(5):1093--1108, 2004. https://doi.org/10.1137/S009753970241096X doi:10.1137/S009753970241096X

    2004 doi

  58. [66]

    Introduction to Circuit Complexity - A Uniform Approach

    Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach . Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. https://doi.org/10.1007/978-3-662-03927-4 doi:10.1007/978-3-662-03927-4

    1999 doi

  59. [67]

    Growth sequences of finite groups III

    James Wiegold. Growth sequences of finite groups III . Journal of the Australian Mathematical Society , 25(2):142–144, 1978. https://doi.org/10.1017/S1446788700038726 doi:10.1017/S1446788700038726

    1978 doi

  60. [68]

    James B. Wilson. The threshold for subgroup profiles to agree is logarithmic. Theory of Computing , 15(19):1--25, 2019. https://doi.org/10.4086/toc.2019.v015a019 doi:10.4086/toc.2019.v015a019

    2019 doi

  61. [69]

    James B. Wilson. Isomorphism testing of permutation groups. Personal communication, Dec. 2024

    2024

  62. [70]

    Marty J. Wolf. Nondeterministic circuits, space complexity and quasigroups. Theoretical Computer Science , 125(2):295--313, 1994. https://doi.org/10.1016/0304-3975(92)00014-I doi:10.1016/0304-3975(92)00014-I

    1994 doi

  63. [71]

    V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich. Graph isomorphism problem. J. Soviet Math. , 29(4):1426--1481, May 1985. https://doi.org/10.1007/BF02104746 doi:10.1007/BF02104746

    1985 doi

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.