Metraipolis › archive › dc_a98d72aba4d9

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.26257
License (as archived)
CC0-1.0
Archived
2026-10-17T19:21:03.764Z
SHA-256 of the archived text
59958c5511a41c539b46e673faf88fc7c431f4a3466610f31ef7fdc4fbc58e40
Stable URL of this page
https://metraipolis.com/documento/dc_a98d72aba4d9

How to cite

Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$\frac{1}{2}$ Circuits and Lower Bounds — arXiv:2608.26257 — arXiv (en), https://arxiv.org/abs/2608.26257 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a98d72aba4d9 (Metraipolis archive dc_a98d72aba4d9, sha256 59958c5511a41c539b46e673faf88fc7c431f4a3466610f31ef7fdc4fbc58e40)
BibTeX
@misc{dca98d72aba4d9,
  title = {Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$frac12$ Circuits and Lower Bounds — arXiv:2608.26257},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.26257},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a98d72aba4d9; sha256 59958c5511a41c539b46e673faf88fc7c431f4a3466610f31ef7fdc4fbc58e40},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.26257. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-28 in cs.DS).
Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.26257 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T19:16:36.842Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).