Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2 1 over 2 Circuits and Lower Bounds
cs.CC, cs.DS, math.GR
Submitted: 2026-08-26
Updated: 2026-10-28
Comments: New result: lower-bound against CNF-of-XORs. 69 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model.
Terminology
Abstract
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 also extend this to a limited class of depth-3 circuits, namely-of- s.) We complement this with upper bounds of uniform depth- 2 1 over 2 circuits of quasipolynomial-size: depth 3 circuits with poly-logarithmic bottom fan-in. A sequence of previous results from 1970-2025 progressively reduced the circuit depth from polynomial to 3 1 over 2; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth- 2 1 over 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.
Sources
- Graph Isomorphism in Quasipolynomial Time
- On the Constant-Depth Circuit Complexity of Generating Quasigroups
- On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
- Presentations of finite simple groups: a quantitative approach
- Algorithms for group isomorphism via group extensions and cohomology
- On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
- Parallel Algorithms for Group Isomorphism via Code Equivalence
- On the Group and Color Isomorphism Problems
- Group Isomorphism with Fixed Subnormal Chains
- Describing finite groups by short first-order sentences
- Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?