Metraipolis › archive › dc_8f309b88cecc

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT — arXiv:2611.07972

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.07972
License (as archived)
CC0-1.0
Archived
2026-11-06T14:54:32.670Z
SHA-256 of the archived text
0f34c7399773bbbcebb6adea2ae3a4bbfc23a94f7619fae07ecff682c6aaccde
Stable URL of this page
https://metraipolis.com/documento/dc_8f309b88cecc

How to cite

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT — arXiv:2611.07972 — arXiv (en), https://arxiv.org/abs/2611.07972 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8f309b88cecc (Metraipolis archive dc_8f309b88cecc, sha256 0f34c7399773bbbcebb6adea2ae3a4bbfc23a94f7619fae07ecff682c6aaccde)
BibTeX
@misc{dc8f309b88cecc,
  title = {A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT — arXiv:2611.07972},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07972},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8f309b88cecc; sha256 0f34c7399773bbbcebb6adea2ae3a4bbfc23a94f7619fae07ecff682c6aaccde},
  year = {2026}
}

Archived text

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

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.07972 — 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-11-06T14:27:27.634Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).