Metraipolis › archive › dc_dfd2e5389eb4

Restrictions of Infinite Circuits — arXiv:2609.14039

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.14039
License (as archived): CC0-1.0
Archived: 2026-10-16T01:38:21.684Z
SHA-256 of the archived text: 8ec0fc2434596d35453a083406bb2207396f291367cecaf50bbb8266ea04307b
Stable URL of this page: https://metraipolis.com/documento/dc_dfd2e5389eb4

How to cite

Restrictions of Infinite Circuits — arXiv:2609.14039 — arXiv (en), https://arxiv.org/abs/2609.14039 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dfd2e5389eb4 (Metraipolis archive dc_dfd2e5389eb4, sha256 8ec0fc2434596d35453a083406bb2207396f291367cecaf50bbb8266ea04307b)

BibTeX

@misc{dcdfd2e5389eb4,
  title = {Restrictions of Infinite Circuits — arXiv:2609.14039},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.14039},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dfd2e5389eb4; sha256 8ec0fc2434596d35453a083406bb2207396f291367cecaf50bbb8266ea04307b},
  year = {2026}
}

Archived text

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

We present a new approach to lower bounds on Borel rank via a connection between Borel sets and infinite circuits. We prove an infinite analog to Håstad's switching lemma called the \emph{restriction lemma}, which shows that by fixing the values of some inputs, we can simultaneously reduce the complexity of one Borel function while largely maintaining the complexity of another. This result provides a purely combinatorial proof of the Borel hierarchy theorem, as well as simple proofs of various Ramsey-like properties of Borel sets and functions. We prove that the restriction lemma is sharp and also discuss counterexamples demonstrating the limitations of the restriction technique, in the context of both Borel functions and $\mathsf{AC}^0$ circuit families.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.LO).
Categorie arXiv: Logic (math.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.14039 — 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-16T01:22:41.479Z dalla pagina https://arxiv.org/catchup/math.LO/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).