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

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least 2ⁿ/(2n), or VP⁰Z≠ VNP⁰Z, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that NP⊆ SIZE[nᵏ] for every constant k≥1. 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 F, we first give a deterministic O(stᵈ⁻¹)-time algorithm for PIT on size-s circuits computing degree-d polynomials in t variables. We further show that, for any fixed d≥2 and ε>0, improving this running time by a factor of tε, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of t1+ε/2 for a polynomial family from VNPF. If nondeterministic PIT instead runs in time sᵒ⁽ᵈ⁾t(1-ε)d for infinitely many degrees d, then the arithmetic lower bound strengthens to VPF≠ VNPF. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time sO(1)t5d/6, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over Z gives a purely arithmetic win-win: either VPZ≠ VNPZ, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.