Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$\frac{1}{2}$ Circuits and Lower Bounds

1 Introduction

• The paper asks whether Group Isomorphism in the Cayley table model belongs to AC0, despite best-known algorithms requiring quasipynomial time in the input length.In this model, the group order is polynomially related to the input length, so |G|^Θ(log |G|) becomes quasipolynomial.Source: §1 · p. 2

1.1 Lower bounds

• Any uniform or non-uniform depth-2 circuit deciding Group Isomorphism requires size |G|^Ω(log |G|), with DNFs requiring exponential size and CNFs requiring |G|^Ω(log |G|).The CNF proof combines an affine-projection reduction from Matrix Rank with bounded-rank matrix-space dimension bounds, while the DNF proof uses the fact that Cayley tables cannot differ in exactly one entry.Source: §1.1 · p. 3
• The lower-bound result also yields the first stated polynomial-size depth-2 circuit lower bound for Latin Square Isotopy.This follows because groups are isotopic exactly when they are isomorphic, as established by Albert.Source: §1.1 · p. 4

1.2 Depth-3 Circuits for Group Isomorphism

• Group Isomorphism has uniform depth-2½ circuits of quasipolynomial size, improving prior depth-3½ circuits [CGLW25] by guessing polylogarithmic-length group encodings and verifying them for both inputs.The method exploits group presentations, composition factors, extension compatibility, and cohomology rather than the generator-enumerator strategy; its quasipolynomial size is slightly larger than n^O(log n) [CGLW25].Source: §1.2 · pp. 4–5
• Assuming the Uniform Short Presentation Conjecture, GpI has a quasipolynomial-size DNF conjoined with a polynomial-size CNF and belongs to ∃polylog(n)AC0.These circuits are weft 2 and 2-tt projection reductions to quasipolynomial-size CNFs, whereas the unconditional circuits are weft 3 with quasipolynomial top fan-in.Source: §1.2 · pp. 4, 6

1.3 Related Work

• The related-work landscape is dominated by generator-enumerator algorithms for groups and quasigroups, while this paper improves depth at the cost of increasing quasipolynomial size.The paper also establishes uniform short presentations for PSU3(q) and Sz(q), which had not previously been shown uniform.Source: §1.3 · pp. 6–8, Table 1 · p. 7
• Nies and Tent [NT17] showed that every finite group has a polylogarithmic-length first-order description, implying that Group Isomorphism is in quasiAC0.Their Σ_m descriptions have length O(log^4 |G|) for constant m; quantifier-to-gate translation and an outer OR over candidate sentences yield quasipolynomial-size constant-depth circuits.Source: §1.3 · pp. 8–9
• The first-order approach does not directly provide the desired shallow circuits because evaluating atomic formulas appears to add a circuit layer, even if the quantifier alternation is reduced.The cited analysis estimates m ≤ 10, usually obtains Σ_3 sentences except for Ree groups, and observes an apparent depth increase to 4, with a comparison to [CGLW25].Source: §1.3 · p. 9
• Subgroup-profile methods cannot characterize all groups using a fixed number of generated subgroups: Glauberman and Grabowski refuted this possibility, and Wilson strengthened the required lower bound to k ≥ log^3 |G| − 2.Gowers and Babai [Bab16, Page 81] posed the fixed-k question; the bound is close to the general generator bound based on the smallest prime divisor p of |G|.Source: §1.3 · p. 9
• Other restricted-model lower bounds include Ω(log |G_m|) variables for identifying an infinite Abelian-group family in first-order logic, a higher-arity extension, and an Ω(|G|) query lower bound [Bsh26].The query bound concerns multiplication-table isomorphism testing in an algebraic model where queries access group elements and natural group operations.Source: §1.3 · p. 9
• The Abelian groups used in these prior lower bounds are essentially products of copies of Z2 and Z4, matching the family used for the paper’s CNF lower bound after imposing a form suitable for a reduction from Matrix Rank.This connects the paper’s lower-bound construction to the finite-model-theoretic and query-complexity examples without claiming identical reductions.Source: §1.3 · p. 9

2.1 Complexity theory

• Complexity theory fixes Boolean circuit classes, uniformity conventions, quasipolynomial-size variants, polylogarithmic-time hierarchies, and reductions used throughout.AC^k uses polynomial-size circuits of depth O(log^k n), while quasiNC uses quasipolynomially many gates with polylogarithmic-time uniformity; Proposition 2.4 places DTIME(t(n)) in ∃O(t(n)^2)AC0 for t(n) ≥ log n.Source: §2.1 · pp. 10–13

2.2 Group theory

• Finite-group preliminaries define composition series, composition factors, straight-line programs, and Cayley-table discrete logarithms within coNTISP(polylog(n), log n)MV.Jordan–Hölder guarantees that composition series share length and composition factors up to isomorphism, while every element generated by S has an SLP of length at most (1 + log |⟨S⟩|)^2.Source: §2.2 · pp. 13–14

2.3 Group Extensions and Cohomology

• Group extensions represent G through a normal subgroup N, quotient Q, outer actions, sections, and normalized 2-cocycles satisfying the cocycle identity.Extension data packages an action T: Q → Aut(N) with a function f: Q × Q → N, and equivalence permits conjugation by a map t: Q → N.Source: §2.3 · pp. 15–16
• Outer action compatibility asks whether quotient automorphisms and subgroup automorphisms, together with inner adjustments, relate two extension actions.Formally, compatibility requires β ∈ Aut(Q) and suitable α and t′ such that T1(q) = α^-1 ◦ t′(β(q)) ◦ T2(β(q)) ◦ α.Source: §2.3 · p. 15
• Lemma 2.12 characterizes isomorphisms G1 → G2 sending specified normal subgroups N1 to N2 through two conditions, including pseudo-congruence of corresponding extension data [GQ17].The extension data consist of actions and factor sets, with pseudo-congruence allowing automorphisms of the normal subgroup and quotient together with a correcting map t: Q → N.Source: §2.3 · p. 16

2.4 Group Presentations

• Presentation length is defined as the total number of generators plus relation-word lengths, while binary encodings and repeated-squaring relations preserve asymptotic efficiency.A word-length O(log^c |G|) presentation yields bit length O(log^c |G| log log |G|) ⊆ eO(log^c |G|), and the extra factor is unnecessary with O(1) generators and length Ω(log |G|).Source: §2.4 · p. 17
• Using presentations for composition factors, lifts, short straight-line programs, relator corrections, and conjugation computations, [BGK+97] construct a presentation of length O(log^{c+1} |G|) for any finite group.The construction assumes presentations of length O(log^c n) for finite simple groups and builds generators and relations across a composition series.Source: §2.4 · pp. 18–19

2.5 Additional preliminaries for the Ree groups 2G2(q)

• The Ree groups 2G2(q) are finite simple groups of order q^3(q^3 + 1)(q − 1), with q = 3^{2k+1}, represented concretely by 7 × 7 matrices [Ree60, KLM01].The recalled representation uses generators involving a Sylow 3-subgroup and the parameter ℓ = 3^k.Source: §2.5 · p. 19
• The Ree groups admit the disjoint Bruhat decomposition 2G2(q) = (HU) ⊔ (HUΥU), with unique parameterizations inside HU and outside HU.Here U consists of products α(a)β(b)γ(c), H normalizes U, and the decomposition supplies a bijective parametrization used later.Source: §2.5 · pp. 20–21

3 Depth-3 Circuits for Group Isomorphism

• Group Isomorphism has uniform depth-3 circuits of quasipolynomial size and polylogarithmic bottom fan-in in the Cayley-table model.Theorem 3.1 places the problem in the stated circuit class for constants c1 and c2.Source: §3 · p. 21
• The Uniform Short Presentation Conjecture further places Group Isomorphism in the corresponding simpler circuit class stated by the second half of Theorem 3.1.This conditional improvement combines the isomorphism procedure with the polynomial-size CNF validity test.Source: §3 · p. 21
• Under the Uniform Short Presentation Conjecture, GpI ∈∃polylog(n)AC0, addressing a question implicit in and highlighted in [CGLW25] up to the exponent of the exponent.The corollary follows by combining the conditional isomorphism result, the validity CNF, and DTIME(polylog(n)) ⊆∃polylog(n)AC0.Source: §3 · p. 21

3.1 The total language and validity of Cayley tables

• Validity of an n×n Cayley table is decidable in ∀log nDTISP(log n log log n, log n) and by a uniform polynomial-size CNF with logarithmic clause width.The verifier checks range, row-distinctness, column-distinctness, and associativity; these conditions characterize group tables.Source: §3.1 · pp. 22–23

3.2 The promise language and testing for isomorphism in the second level of the Polylogarithmic-Time Hierarchy

• Given multiplication tables of groups G and H, isomorphism is decidable in ∃polylog(n)∀polylog(n)DTIME(polylog(n)); with uniform short presentations for G’s composition factors, it is decidable in ∃polylog(n)DTIME(polylog(n)).The procedure guesses composition-factor data, presentations, generators, and straight-line programs, then verifies both groups against an order-matched presentation [BGK+97, Theorem 8.3].Source: §3.2 · pp. 23, 26
• For Ree composition factors lacking uniform short presentations, the test uses universal quantification over multiplication-table relators, bounded-length SLP enumeration, and an efficiently invertible bijection to maintain section consistency.Correctness relies on the Babai–Szemerédi Reachability Lemma, efficient discrete logarithms, and non-Abelian cohomology [GQ17].Source: §3.2 · p. 24
• The verifier validates standard names by checking primality, field parameters, polynomial irreducibility, and primitive-root conditions in polylogarithmic time.It uses AKS04 for primality and Rabin’s irreducibility test [Rab80, Lemma 1], with repeated squaring and Euclidean-algorithm checks.Source: §3.2 · pp. 27–28
• For non-Ree composition factors, the verifier checks guessed presentations and relators, establishing isomorphisms between successive extensions that preserve the generator correspondence.Uniform short presentations provide presentations for the simple factors, while additional co-nondeterministic checks ensure nontrivial quotients when needed.Source: §3.2 · pp. 29, 31
• For Ree factors 2G2(q), cohomological verification checks normality, action compatibility, quotient identification, and equality of the associated 2-cocycles.Sections derived from generators define the extension data, and co-nondeterministically guessed straight-line programs witness quotient and cocycle evaluations.Source: §3.2 · pp. 29–30
• Passing all checks inductively extends the generator map through the composition series, yielding G ∼= H and an isomorphism extending Φm.For Ree factors, order-product verification upgrades quotient surjections to isomorphisms, after which Lemma 2.12 completes the extension argument.Source: §3.2 · pp. 30–32
• At each composition-series stage, the algorithm uses polylog(n) existential bits, additionally polylog(n) universal bits for Ree factors, and deterministic polylog(n) time.The number of stages satisfies m ≤⌈log |G|⌉, and the verification uses logarithmic space apart from possibly constructing presentations under the Uniform Short Presentation Conjecture.Source: §3.2 · pp. 29, 32
• If all composition factors have uniform short presentations, the verifier can omit the co-nondeterministic bits needed for factors lacking such presentations.This includes the Ree case if the Uniform Short Presentation Conjecture holds for all finite simple groups.Source: §3.2 · p. 32
• Without uniform Short Presentation Conjecture assumptions, Group Isomorphism has non-uniform circuits combining a quasipolynomial-size DNF with a polynomial-size CNF.The advice contains short presentations of all finite simple groups of order at most n, using O(n polylog(n)) bits.Source: §3.2 · p. 32
• Upgrading uniformity from DTIME(polylog(n)) to DTISP(polylog(n), log(n)) correspondingly strengthens Proposition 3.4.In the non-uniform setting, standard-name conversion can query the relevant short presentation from advice instead.Source: §3.2 · p. 32
• The co-nondeterministic verification bits are necessary when Ree and non-Ree composition factors coexist, unless uniform short presentations for Ree factors are available.Without those bits, size checks can balance incorrectly; with uniform Ree presentations or no Ree factors, the checks force each quotient to match its guessed simple group.Source: §3.2 · p. 32

4.1 Exponential DNF lower bound

• Every DNF deciding validity, and hence total Group Isomorphism, requires at least 2^(n log n−O(n)) terms for groups of order n.The argument uses the absence of two quasigroup tables differing in one entry, forcing every term to specify an entire valid table.Source: §4 · p. 33, §4.1 · p. 34

4.2 Quasi-polynomial CNF lower bound

• Promise Group Isomorphism on groups of order n = 2^(2k) requires CNFs of size n^Ω(log n), even for Abelian groups of exponent 4.The reduction maps a k × k binary matrix M to a group whose isomorphism type is determined by rank(M), with each output bit depending on at most one row of M.Source: §4 · p. 33, §4.2 · pp. 34–35

4.1 Exponential DNF lower bound

• Under the Uniform Short Presentation Conjecture, Validity Testing and Group Isomorphism have polynomially equivalent DNF complexity up to a quasipolynomial factor.Validity Testing DNF size f(n) yields a Group Isomorphism DNF of size f(n)2^(n polylog(n)).Source: §4.1 · p. 33

4.2.2 Returning to the lower bound

• Row-cube falsifying sets have contiguous attainable ranks, so avoiding rank s + 1 while covering rank s bounds their dimension by ks.This combines the row-wise affine structure of restricted CNF clauses with the affine-subspace rank-dimension theorem.Source: §4.2.2 · p. 37, §4.2.1 · p. 37
• There are at least q^(r(2k−r)) k × k matrices over F_q of rank at most r, forcing exponentially many clauses to cover all lower-rank matrices without covering rank k/2 matrices.Optimizing at s = k/2 yields the stated n^Ω(log n) CNF lower bound.Source: §4.2 · p. 35, §4.2.2 · pp. 37–38
• Baer’s correspondence reduces isomorphism of class-2 exponent-p groups to simultaneous-change-of-basis orbits of skew-symmetric matrix tuples.For tensors T and S, the associated groups are isomorphic exactly when S = h · T for some h ∈ GLℓ(p) × GLk(p).Source: §4.2.2 · pp. 38–39
• Tensor orbit sizes are at most p^O(k^2+ℓ^2), while the full parameter space has size p^Θ(k^3) when ℓ≍k, so fixed-orbit covering arguments are insufficient.The natural covering object is instead the two-input isomorphism relation Y = {(T,S) : T ∼= S}.Source: §4.2.2 · p. 39
• The direct affine-subspace strategy fails because one can construct a yes-free affine subspace of X × X whose codimension is too small in the balanced regime.Taking tensors with a fixed radical vector in one factor and a fixed full-rank skew-symmetric form in the other yields a yes-free subspace, since radical dimension is an isomorphism invariant.Source: §4.2.2 · p. 39

4.3 QuasiCNF implies Group Isomorphism is in coNP

• Quasipolylogarithmic-time algorithms with universal quantification over polynomially many choices lie in coNP, so such an algorithm for Group Isomorphism would resolve its coNP membership.Group Isomorphism in coNP remains a significant open question for general finite groups; for solvable groups, Arvind and Torán obtained related protocols and conditional NP ∩ coNP membership.Source: §4.3 · p. 39

5 Uniformity of the Hulpke–Seress Short Presentations for 2A2(q) = PSU3(q)

• A presentation of PSU3(q) can be constructed in DTIME(polylog(|G|)) with word length O(log2 q) = O(log2 |G|).This is Proposition 5.1 for q = p^e > 2 and G = 2A2(q) = PSU3(q).Source: §5 · p. 40

5.2 Uniform presentation for the Borel subgroup of PSU3(q)

• From the standard name for PSU3(q), a presentation of the Borel subgroup ⟨U, h⟩ is constructible in DTIME(polylog(q)) with word length O(log2 q).The construction uses generators for Z(U), lifts of a basis of U/Z(U), and a generator normalizing them; its relations have total binary-exponent length O(log2 q).Source: §5.2 · pp. 42, 44, 45
• For g = u(x, y) ∈ U, constructive membership yields a word evaluating to g in DTIME(polylog(q)) with binary-exponent length O(log q).The parameters are read from the matrix, and Gaussian elimination over Fp computes the coefficients for the quotient and central generators; repeated squaring evaluates powers.Source: §5.2 · pp. 43–44

5.3 Proof of Proposition 5.1

• The full PSU3(q) presentation is completed by making the three or seven additional Hulpke–Seress relations [HS01, Theorems 15–16] uniform using explicitly known powers of ρ.The construction defines suitable field elements and verifies that the relevant first coordinates lie in the required trace-related sets.Source: §5.3 · p. 45
• The construction computes norm preimages, including cube-compatible ones when d = 3, using operations that take time polynomial in log q.For odd p, deterministic square-root extraction handles square and nonsquare cases; the d = 3 construction additionally produces cube elements.Source: §5.3 · pp. 45–46
• Construction 5.7 adds the generator b_t and relators tailored to d = 1 or d = 3, using three or seven R-relations, respectively.For d = 1, the relations are R(a), R(c), and R(a′); for d = 3, they use R(c) and the corresponding relations for the three cube classes.Source: §5.3 · p. 46
• The resulting presentation presents PSU3(q): the defining matrices satisfy all relations and generate the group, while [HS01, Theorems 15–16] complete the d = 1 and d = 3 cases.The d = 1 case derives R(a), R(b), and R(ab); the d = 3 case derives the relations for all three cube classes.Source: §5.3 · p. 46
• The complete presentation has binary-exponent length O(log^2 q), converts to word length O(log^2 |G|) via [BGK+97, Remark 1.3], and is produced in DTIME(polylog(n)).Field operations, coordinate expansions, and exponent computations are polynomial-time in log q; since log |G| = Θ(log q), the asymptotic bound transfers to |G|.Source: §5.3 · p. 47

6 Uniformity of the Guralnick–Kantor–Kassabov–Lubotzky Short Presentation for the Suzuki groups 2B2(q) = Sz(q)

• For q = 2^(2k+1), a DTIME(polylog(q)) algorithm given the standard name of Sz(q) constructs a short presentation.This establishes uniformity for the bounded presentation previously supplied by [GKKL08].Source: §6 · p. 47

6.1 Preliminaries: polynomial notation

• The finite-field preliminaries compute minimal and coordinate polynomials, Frobenius powers, and polynomial words in DTIME(polylog(q)).For p = 2, the resulting polynomial words have length O(log q).Source: §6.1 · p. 48

6.2 Preliminaries on the Suzuki groups

• The construction starts from the seven-generator, 43-relation presentation of Sz(q) from [GKKL08] and makes every word constructible uniformly.The group-theoretic setup uses the Suzuki subgroup U and its Borel subgroup, while correctness remains due to [GKKL08].Source: §6.2 · pp. 48–50

6.3 Proof of Proposition 6.1

• Constructive membership in U yields words of length O(log q) in four generators, computable in DTIME(polylog(q)), enabling uniform generation of the presentation’s relators.Central correction terms and the remaining relations are generated using these words, finite-field computation, and Suzuki’s explicit formulas [Suz62].Source: §6.3 · pp. 50–52

Upper Bounds

• Group Isomorphism lies in the second level of the polylogarithmic-time hierarchy, giving uniform AC circuits of depth-2½ and quasipolynomial size.This improves the previous depth-3½ upper bound for Quasigroup Isomorphism due to Collins, Grochow, Levet, and Weiß [CGLW25].Source: §7 · p. 52

Limitations and Open Questions

• Extending the upper bound to quasigroups appears out of reach because the method depends on group composition series, the Classification of Finite Simple Groups, and short group presentations.There is no comparable composition-series theory for general quasigroups, and even O(1)-generation of all finite simple quasigroups is open.Source: §7 · pp. 52–53

Upper Bounds

• The depth-2½ construction establishes uniform short-presentation tools for PSU3(q), Suzuki, and Ree groups, including polylogarithmic-time constructive membership in suitable Borel subgroups.Short presentations for PSU3(q) and Suzuki groups are uniformized from [GKKL08], while analogous tools handle the Ree groups.Source: §7 · p. 53

Lower Bounds

• Verifying that a multiplication table defines a group or Latin square requires exponential-size DNFs, while Abelian-group isomorphism requires CNFs of size n^Ω(log n).The CNF lower bound relies on Seguins Pazzis’s bounded-rank matrix-space dimension result [dSP10].Source: §7 · p. 53
• These lower bounds extend to Latin Square Isotopy, whose prior upper bound matched the depth-3½, n^O(log n) result for Quasigroup Isomorphism [CGLW25].The paper notes that switching-lemma approaches remain possible, whereas low-depth reductions from Parity or Majority are ruled out by the ∃log^2 nFOLL upper bound.Source: §7 · p. 53

Limitations and Open Questions

• The paper leaves open whether Group Isomorphism is outside AC^0, whether stronger CNF or depth-3 lower bounds hold, and whether promised Abelian-group isomorphism requires super-polynomial DNFs.Because validity testing has polynomial-size CNFs, the CNF and depth-3 questions are equivalent to their promise versions.Source: §7 · pp. 53–54

• The calculations were executed in Wolfram 14.3.0.0 on a 64-bit ARM Mac OS X platform on 20 Aug 2026.Source: A Mathematica code to verify matrix… · p. 54
• The code defines an AntidiagonalMatrix function for list or sparse-array inputs, including diagonal offsets and specified matrix dimensions.The implementation reverses a diagonal matrix to produce the antidiagonal form.Source: A Mathematica code to verify matrix… · p. 54
• It sets up the 2G2(q) generating set from Lemma 3.5 using AlphaMat, diagonal matrix terms, and an antidiagonal matrix TMat.The symbolic entries include powers of a, lam, and L, with TMat defined from a seven-entry list of -1 values.Source: A Mathematica code to verify matrix… · pp. 54–55
• L remains unconstrained because the needed elements appear symbolically without imposing its Ree-group semantics.The final commands extract selected entries from products involving HMat, AlphaMat, BetaMat, GammaMat, and TMat to verify the required calculations.Source: A Mathematica code to verify matrix… · p. 55