Publication
A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT
Preprint, 2026. PDF
Abstract
We prove unconditionally that either \(\mathsf{NE}\) contains a language requiring Boolean circuits of size at least \(2^n/(2n)\), or \(\mathsf{VP}^0_{\mathbb{Z}} \neq \mathsf{VNP}^0_{\mathbb{Z}}\), a constant-free version of Valiant’s conjecture over the integers. The Boolean alternative implies that \(\mathsf{NP} \not\subseteq \mathsf{SIZE}[n^k]\) for every constant \(k \ge 1\). Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (\(\mathsf{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 \(\mathsf{PIT}\) on size-\(s\) circuits computing degree-\(d\) polynomials in \(t\) variables. We further show that, for any fixed \(d \ge 2\) 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 \(\mathsf{VNP}_{\mathbb{F}}\). If nondeterministic \(\mathsf{PIT}\) instead runs in time \(s^{o(d)} t^{(1-\varepsilon)d}\) for infinitely many degrees \(d\), then the arithmetic lower bound strengthens to \(\mathsf{VP}_{\mathbb{F}} \neq \mathsf{VNP}_{\mathbb{F}}\). Over the integers, we give a deterministic \(\mathsf{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 \(\mathsf{NP}\) algorithm for \(\mathsf{PIT}\) over \(\mathbb{Z}\) gives a purely arithmetic win–win: either \(\mathsf{VP}_{\mathbb{Z}} \neq \mathsf{VNP}_{\mathbb{Z}}\), or constant-degree polynomials of maximum circuit complexity can be constructed in \(\mathsf{FNP}\).
Along the way, we show that arithmetic circuits of size \(s(N)\) for the permanent, or for an explicit family in \(\mathsf{VNP}\), give perfectly complete input-oblivious Merlin–Arthur protocols running in time \(s(O(n))\, n^{O(1)}\) for \(3\text{-}\mathsf{UNSAT}\) with \(O(n)\) clauses; thus ruling out faster protocols yields arithmetic lower bounds that scale with the protocol’s running time.