arXiv:2608.26257 · v2

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

首次提交 2026-08-27 02:00

版本更新 2026-10-29 06:05

雷达观测 2026-10-30 11:25

摘要

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 $\textsf{CNF}$-of-$\textsf{XOR}$s.) We complement this with upper bounds of uniform depth-$2\frac{1}{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\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.

作者备注：New result: lower-bound against CNF-of-XORs. 69 pages