Metraipolis › archive › dc_c33da03ae1cb

Top-Down Lower Bounds for All Depths — arXiv:2609.38677

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.38677
License (as archived)
CC0-1.0
Archived
2026-10-07T15:17:56.726Z
SHA-256 of the archived text
ac13ba8f6451359eccae824d72c00f280b3d408320240278878985b685e14a7f
Stable URL of this page
https://metraipolis.com/documento/dc_c33da03ae1cb

How to cite

Top-Down Lower Bounds for All Depths — arXiv:2609.38677 — arXiv (en), https://arxiv.org/abs/2609.38677 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c33da03ae1cb (Metraipolis archive dc_c33da03ae1cb, sha256 ac13ba8f6451359eccae824d72c00f280b3d408320240278878985b685e14a7f)
BibTeX
@misc{dcc33da03ae1cb,
  title = {Top-Down Lower Bounds for All Depths — arXiv:2609.38677},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.38677},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c33da03ae1cb; sha256 ac13ba8f6451359eccae824d72c00f280b3d408320240278878985b685e14a7f},
  year = {2026}
}

Archived text

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

We prove that Parity requires $2^{n^{\Omega(1)}}$ size De Morgan circuits of constant depth using a new method which is completely "top-down" in the sense of [HJP95]. The proof relies crucially on the core ideas developed in a line of work [HJP95, PPZ99, MW19, GRSS24] which previously established top-down lower bounds for circuits of depth 3 and 4. We first present a proof of a lower bound $\exp(n^{3^{-d}})$. In this case, nearly all of the relevant combinatorial ideas necessary for the proof are already present in some form in [GRSS24]. We then present two extensions of this argument, the first achieving a lower bound $\exp(\epsilon_d n^{1/(2d-2)})$ for some $\epsilon_d>0$ depending only on $d$, and the second achieving the essentially tight lower bound $\exp(\epsilon_d n^{1/(d-1)})$. These improved results each hinge on establishing a key lemma which quantifies the extent to which a high entropy random variable in $\{0,1\}^n$ will look close to uniform after projecting it onto a random small set of coordinates $R \subseteq [n]$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.38677 — 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-07T14:51:27.471Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).