PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Joshua A. Grochow, Gülce Kardeş, Michael Levet

arXiv:2608.26257v1cs.CCcs.DS

TL;DR

The paper studies low-depth circuit complexity for Group Isomorphism in the Cayley-table model, addressing elusive depth-2 lower bounds and improving upper-bound depth. It develops a group-specific encoding and verification strategy, obtaining nontrivial lower bounds and uniform quasipolynomial-size depth-2½ circuits.

  • Problem

    Circuit lower bounds for Group Isomorphism had remained elusive even at depth 2, despite interest in whether the problem lies in AC0.

  • Method

    The approach combines an affine-projection reduction from Matrix Rank with bounded-rank matrix-space results, while upper bounds verify guessed polylogarithmic-length group encodings.

  • Results

    The paper proves nontrivial DNF and CNF lower bounds for Group Isomorphism-related problems and places Group Isomorphism in the second level of the polylogarithmic-time hierarchy, yielding uniform depth-2½ circuits of quasipolynomial size.

  • Takeaways & Limitations

    The results provide the first nontrivial circuit lower bounds against Group Isomorphism and improve the upper-bound depth over the previous best result for the more general Quasigroup Isomorphism problem.

  • Takeaways & Limitations

    The lower-bound strategy faces structural obstacles when extended from matrices to tensors, including large affine subspaces that undermine the analogous rank argument.

Abstract

from arXiv · show

In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. We complement this with upper bounds of uniform depth-$2\frac{1}{2}$ circuits of quasipolynomial-size. A sequence of previous results from 1970-2025 progressively reduced the circuit depth from polynomial to $3\frac{1}{2}$; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth-$2\frac{1}{2}$ construction follows a fundamentally different strategy that exploits structure more specific to groups. We guess a composition series for each group, together with generators for its terms and the isomorphism types of its composition factors. We then inductively verify that the corresponding extensions at each level of the two composition series are compatible. A central part in this approach brings to bear the extensive work on the Short Presentation Conjecture, in tandem with the algorithmic theory of group extensions and cohomology.

1 Introduction

The paper establishes the first Boolean-circuit lower bounds for Group Isomorphism and improves its upper-bound depth in the Cayley table model. Its upper-bound strategy is group-specific, while the lower bounds use affine reductions and matrix-rank structure.

  • 1 Introduction: Group Isomorphism asks whether two groups are equivalent under relabeling, with the paper studying multiplication-table inputs and uniform low-depth circuits.In the Cayley table model, quasipolynomial running times in group order are quasipolynomial in the input length.
  • 1 Introduction: AC0 membership remains open, while prior depth-2 lower bounds for Group Isomorphism were unavailable despite the problem’s importance.A general quasigroup upper bound also blocks standard Parity- or Majority-based AC0 lower-bound strategies.
  • 1.1 Lower bounds: |G|^Omega(log |G|) size is required by every uniform or non-uniform depth-2 circuit family deciding Group Isomorphism.DNFs require exponential size, while CNFs require |G|^Omega(log |G|) size.
  • 1.1 Lower bounds: The CNF lower bound combines an affine-projection reduction from Matrix Rank with bounds on affine spaces of bounded-rank matrices.The DNF lower bound instead uses the fact that two group or quasigroup Cayley tables cannot differ in exactly one entry.
  • 1.2 Depth-3 Circuits for Group Isomorphism: Depth-2 1/2 uniform circuits of quasipolynomial size decide Group Isomorphism, improving the previous depth bound for the more general Quasigroup Isomorphism problem.Assuming the Uniform Short Presentation Conjecture, the bound improves to a conjunction of a quasipolynomial-size DNF and polynomial-size CNF.
  • 1.2 Depth-3 Circuits for Group Isomorphism: The upper-bound method guesses a polylogarithmic encoding shared by both groups, rather than enumerating generating sets, and cannot extend to quasigroups because short encodings are information-theoretically impossible there.The construction relies on short presentations and verifies the guessed group structure.

2 Preliminaries

The preliminaries define the circuit models, uniformity conventions, and complexity classes used throughout, then relate low-time computation to shallow circuits and group-isomorphism extensions.

  • Circuit complexity: The paper uses Boolean circuits over AND, OR, and NOT gates, distinguishing AC^k, NC^k, and SAC^k by depth and fan-in restrictions.AC^k permits arbitrary fan-in, NC^k restricts AND and OR fan-in to two, and SAC^k allows unbounded OR fan-in but fan-in-two AND gates.
  • Uniformity and quasipolynomial size: Quasipolynomial-size circuit classes use 2^{O(log^k n)} gates and DTIME(polylog(n))-uniformity rather than DLOGTIME uniformity.The paper notes that O(log n)-bit gate indices are insufficient for quasipolynomial-size circuits.
  • Bounded nondeterminism: Bounded-nondeterminism classes quantify over witnesses of length O(log^i n), with existential and universal variants defined over an underlying complexity class.The paper places both ∃log^i nFOLL and ∀log^i nFOLL inside quasiFOLL.
  • Time-to-circuit translations: DTIME(t(n)) decision problems can be represented by depth-t(n) decision trees and CNFs or DNFs with 2^{t(n)} clauses or terms.Each clause or term has width t(n).
  • Time-to-circuit translations: For t(n) ≥ log n, every DTIME(t(n)) problem belongs to ∃O(t(n)^2)AC^0.The construction guesses a t(n) × t(n) computation-history array and verifies local consistency in AC^0, including random-access input queries.
  • Group-theoretic preliminaries: For groups with designated normal subgroups, an isomorphism mapping one subgroup to the other is characterized by two necessary and sufficient conditions.This extension criterion is stated as Lemma 2.12 and supports the paper’s inductive group-isomorphism arguments.

3 Depth-3 Circuits for Group Isomorphism

The paper establishes a quasipolynomial-size depth-3 upper bound for Group Isomorphism, with a stronger conditional form under the Uniform Short Presentation Conjecture. Its construction verifies group-table validity and inductively tests compatible extensions along composition series.

  • Group Isomorphism belongs to uniform depth-3 circuits of quasipolynomial size and polylogarithmic bottom fan-in.
  • Under the Uniform Short Presentation Conjecture, the upper bound improves to a conjunction of a quasipolynomial-size DNF and polynomial-size CNF.
  • Validity of Cayley tables: A polynomial-size, logarithmic-width CNF verifies that an input table encodes a group operation by checking range, row-distinctness, column-distinctness, and associativity.
  • Validity of Cayley tables: The validity checks use polynomially many clauses, including O(n^3) range, O(n^4) row-distinctness, O(n^4) column-distinctness, and O(n^5ℓ) associativity clauses.Each clause has width O(ℓ), yielding a uniform polynomial-size CNF.
  • Isomorphism testing: Given group tables, the isomorphism test uses polylogarithmic existential and universal quantification with deterministic polylogarithmic-time computation.If composition factors admit uniform short presentations, the universal quantifier is unnecessary.
  • Isomorphism testing: The inductive verification relies on an efficiently invertible bijection to keep choices of sections and cohomology classes consistent across universal branches.At each stage, the algorithm checks whether the next map extends to an isomorphism between successive composition factors.

4 Lower Bounds

The paper establishes exponential DNF and quasipolynomial CNF lower bounds for Group Isomorphism, including the first nontrivial Boolean-circuit lower bounds. The CNF argument reduces Matrix Rank to isomorphism of specially constructed Abelian groups and uses bounded-rank matrix-space results, while tensor extensions face structural obstacles.

  • DNF lower bounds: 2n log n−O(n) terms are necessary for DNFs recognizing valid group Cayley tables, and the same lower bound transfers to Group Isomorphism.The validity lower bound follows because distinct quasigroup tables cannot differ in one entry; each DNF term must therefore specify an entire valid table.
  • DNF lower bounds: 2n2 log n−O(n2) terms are necessary for DNFs recognizing valid Latin squares, showing an analogous stronger lower bound for quasigroups.Validity testing of quasigroup tables reduces to Quasigroup Isomorphism by a DLOGTIME-uniform projection reduction.
  • CNF lower bounds: nΩ(log n) size is necessary for CNFs solving promise Group Isomorphism on groups of order n = 2^2k.The proof constructs Abelian 2-groups GM whose isomorphism types encode rank over F2, then applies affine bounded-rank matrix-space bounds.
  • CNF lower bounds: The reduction maps a binary matrix M to a group GM whose isomorphism type is determined exactly by rank(M).GM is an Abelian 2-group of exponent at most 4, with rank(M) equal to the number of Z4 factors; each output bit depends on at most one row of M.
  • CNF lower bounds: Row-cubes have contiguous rank sets, so a row-cube containing rank s but no rank s+1 matrix has dimension at most ks.This structural lemma bounds the size of clause-falsifying regions and supports the covering argument yielding the CNF lower bound.
  • Obstacles and implications: The tensor analogue of the matrix covering argument fails on the full tensor space because fixed tensor orbits are asymptotically thinner than generic matrix rank layers.The paper therefore identifies the two-input isomorphism relation as the natural object for a possible tensor covering argument.
  • Obstacles and implications: A quasipolynomial CNF upper bound would place the relevant Group Isomorphism complexity class inside coNP.The stated inclusion is ∀logc nDTIME(polylog(n)) ⊆ coNP.

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

This section establishes uniform, polylogarithmic-time construction of short presentations for PSU3(q), including its Borel subgroup and the full group.

  • Uniform presentation of PSU3(q): A presentation of PSU3(q) has word length O(log2 |G|) and can be constructed in DTIME(polylog(|G|)).This follows from the explicit uniform construction for q = p^e and log |G| = Θ(log q).
  • Uniform presentation of the Borel subgroup: The Borel subgroup ⟨U, h⟩ has a uniformly constructible presentation of word length O(log2 q).The construction uses generators for Z(U), lifts of a basis of U/Z(U), and h, together with explicit relations.
  • Uniform presentation of the Borel subgroup: Uniform generators for U/Z(U) are obtained by separating the cases d = gcd(3, q + 1) = 1 and d = 3.Conjugation by h produces elements whose second parameters form an Fp-basis of Fq2.
  • Uniform presentation of the Borel subgroup: Given a matrix g ∈ U, the algorithm computes a decomposition word decU(g) in DTIME(polylog(q)).Gaussian elimination and repeated squaring yield binary-exponent length O(log q).
  • Verification: The resulting presentation is validated by mapping its generators to matrices that satisfy the defining relations and generate PSU3(q).The proof obtains an epimorphism from the presented group to PSU3(q).

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

This section makes the known short presentation of the Suzuki groups Sz(q) uniform by showing that its relators can be generated in polylogarithmic time.

  • Uniform Suzuki-group presentation: A DTIME(polylog(q)) algorithm constructs a short presentation for Sz(q) from its standard name.The result applies for q = 2^(2k+1).
  • Polynomial word notation: Polynomial word notation expresses group elements through products of conjugates, enabling compact words over selected generators.For g(x) = Σg_i x^i, [[u^g(x)]]_h is the ordered product of conjugates u^{g_i h^i}.
  • Uniform field computations: Field procedures, including minimal-polynomial and coordinate-polynomial computation, run in DTIME(polylog(q)).These procedures support the construction of the words appearing in the presentation.
  • The known presentation: The underlying presentation has 7 generators and 43 relations.Its correctness is due to the previously established presentation, while this section proves uniformity.
  • Constructive membership in U: Constructive membership in U yields words of length O(log q) for elements U(A, B), computable in DTIME(polylog(q)).The words use four generators and evaluate to the target element U(A, B).
  • Uniformity proof: All relators can therefore be output uniformly in DTIME(polylog(n)).Fixed relators and logarithmic-length polynomial words are generated using the computed field data.

7 Conclusion and Open Questions

The paper places Group Isomorphism in the second level of the polylogarithmic-time hierarchy, yielding uniform depth-2½ quasipolynomial-size circuits, and establishes nontrivial lower bounds. Its approach relies on group-specific structure and leaves several depth and size questions open.

  • Upper Bounds: Group Isomorphism belongs to the second level of the polylogarithmic-time hierarchy and has uniform AC circuits of depth-2½ and size n^polylog(n).The bottom level has polylogarithmic fan-in.
  • Upper Bounds: The upper-bound strategy depends on composition series for groups, the Classification of Finite Simple Groups, and short presentations.These ingredients do not extend naturally to general quasigroups.
  • Open Questions: The closer-to-depth-2 result is conditional on the Uniform Short Presentation Conjecture, whose claimed solution has not yet been published.The paper distinguishes this conditional progress from its unconditional depth-2½ upper bound.
  • Lower Bounds: The paper proves exponential-size DNF lower bounds for validity testing of group or Latin-square multiplication tables and n^Ω(log n)-size CNF lower bounds for Abelian-group isomorphism.The CNF argument uses bounds on affine spaces of matrices of bounded rank.
  • Lower Bounds: The lower bounds also apply to Latin Square Isotopy, whose previous upper bound matched that for Quasigroup Isomorphism.This extends the lower-bound results beyond Group Isomorphism.

A Mathematica code to verify matrix calculations symbolically in 2G2(q)

The appendix uses Mathematica code to define matrix constructions and verify symbolic calculations for the Ree groups 2G2(q). It sets up the generating set from Lemma 3.5 and checks selected matrix entries.

  • Execution Environment: The code was executed in Wolfram 14.3.0.0 on macOS ARM64 on 20 August 2026.This records the computational environment used for the symbolic verification.
  • Matrix Utilities: A custom AntidiagonalMatrix function is defined through diagonal-matrix reversal for vectors, offsets, and rectangular dimensions.The implementation supports list or sparse-array inputs.
  • Generating Set: The code sets up the generating set of 2G2(q) specified by Lemma 3.5.The displayed AlphaMat definition is one component of this setup.
  • Symbolic Setup: The diagonal and antidiagonal matrices retain L as an unconstrained symbolic variable during the calculations.The authors report that simplification using the semantic meaning of ℓ was unnecessary for obtaining the desired elements.
  • Verification: The final calculations extract selected entries from products involving HMat, AlphaMat, BetaMat, GammaMat, and TMat.These products verify the needed matrix identities symbolically.
Loading 2608.26257v1…