Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-21/2 Circuits and Lower Bounds
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 textsfCNF-of-textsfXORs.) We complement this with upper bounds of uniform depth-21/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 31/2; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth-21/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.
Related
- Gluing diagrams part 1: A constructive solution for the Higman-Thompson group isomorphism problem
- Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
- On the Twisted Group Ring Isomorphism Problem for isoclinic groups
- Polylogarithmic bound for the Gyárfás-Sumner conjecture
- Certified exact bounds for adaptive quantitative group testing with two defectives
BibTeX
@misc{grochow2026group,
title = {{Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$\frac12$ Circuits and Lower Bounds}},
author = {Joshua A. Grochow and Gülce Kardeş and Michael Levet},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.26257},
eprint = {2608.26257},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.26257},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-21/2 Circuits and Lower Bounds
AU - Joshua A. Grochow
AU - Gülce Kardeş
AU - Michael Levet
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2608.26257
UR - https://arxiv.org/abs/2608.26257
AB - 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 textsfCNF-of-textsfXORs.) We complement this with upper bounds of uniform depth-21/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 31/2; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth-21/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.
ER -