{"id":"arxiv/2608.26257","url":"https://arxiv.org/abs/2608.26257","tags":["cs.CC","cs.DS","math.GR"],"score":0,"title":"Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$\\frac{1}{2}$ Circuits and Lower Bounds","domain":"cs.CC","source":"arxiv","authors":["Joshua A. Grochow","Gülce Kardeş","Michael Levet"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-26","reactions":{}}