REVIEW
A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT
Computational Complexity · Submitted 5 Nov 2026 · 98 references
Pith's verdict: Huge unconditional win-win, but the key set-multilinear PIT lemma has a real arithmetic error in the proof as written; probably repairable, but Theorem 1 currently rests on an unproved speed-up.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
This paper proves, with no derandomization assumption, that at least one of two major conjectures is true: near-maximal circuit hardness for NE or a constant-free VP-versus-VNP separation over the integers.
The reading
What carries the argument
Three objects carry the argument. (1) Partition polynomials: for a list of tables $S_1,\dots,S_d$ over $r$ Boolean variables, $Z_S(w)=\sum_{\mu\in\{0,1\}^r}\prod_{j=1}^d w_{j,\mu|_{S_j}}$; a 3-CNF formula is unsatisfiable exactly when a specialized such polynomial is identically zero, and these polynomials are downward self-reducible, so they replace the permanent as the engine of the connection to lower bounds [KI04] and keep the identity tests at low, choosable degree. (2) A universal polynomial $U\in\mathrm{VNP}_{\mathbb{Z}}$ that contains every partition polynomial as a projection, so a single small-circuit assumption or construction covers all polynomials the proof needs. (3) The new deterministic zero-test for syntactically set-multilinear circuits over the integers (Theorem 5): over $\mathbb{Z}$, a polynomial is zero iff the sum of the squares of its coefficients is zero, and the algorithm computes this sum without expanding the polynomial. It uses a heavy-gate decomposition (Lemma 8.4) that writes the output as a sum of products splitting the $d$ blocks into two parts of between $d/3$ and $2d/3$ blocks each, and an inner-product speedup (Lemma 8.5) that sums indices in the better of two orders, saving $m^{\lceil d/6\rceil}$ operations and yielding the $m^{5d/6}$ running time the main theorem needs.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is Theorem 1: with no derandomization hypothesis, at least one of $\mathrm{NE}\not\subseteq \mathrm{SIZE}[2^n/(2n)]$ and $\mathrm{VP}^0_{\mathbb{Z}} \ne \mathrm{VNP}^0_{\mathbb{Z}}$ holds. The proof argues by assuming $\mathrm{VP}^0_{\mathbb{Z}} = \mathrm{VNP}^0_{\mathbb{Z}}$, which yields small constant-free circuits of polynomial formal degree for the partition polynomials $Z_{T_N}$; these polynomials encode 3-CNF satisfiability and are downward self-reducible, so the equality assumption combined with the new set-multilinear PIT algorithm (Theorem 5) yields a nondeterministic algorithm that decides unsatisfiability of Boolean circuits of size $2^{\rho n}$ in time $O(2^{(1-\rho)n})$. Through the algorithms-to-lower-bounds method [Wil13, MW18, Che25], such a satisfiability algorithm certifies truth tables of high circuit complexity at infinitely many input lengths, which forces $\mathrm{NE}\not\subseteq \mathrm{SIZE}[2^n/(2n)]$. The over-the-integers identity tests are what make the win–win unconditional: they run in deterministic time $m^{d-\lceil d/6\rceil}\cdot(dsL\log(2m))^{O(1)}$ on syntactically set-multilinear circuits, and every circuit produced along the way has coefficients short enough for the test to handle.
Load-bearing premise
The load-bearing premise is that the new deterministic zero-test for syntactically set-multilinear circuits over the integers (Theorem 5) is correct with its stated running time $m^{d-\lceil d/6\rceil}$ and its bounds on intermediate integers; the heavy-gate decomposition of Lemma 8.4 and the inner-product speedup of Lemma 8.5 are new and carry the whole unconditional reduction, so a subtle error in either would leave the NE lower bound of Theorem 1 dependent on an unproved algorithmic step.
Editorial extensions
If this is right
- If the Boolean alternative holds, $\mathrm{NE}\not\subseteq \mathrm{SIZE}[2^n/(2n)]$; by padding this already implies $\mathrm{NP}\not\subseteq \mathrm{SIZE}[n^k]$ for every constant $k\ge 1$, giving the first near-maximal lower bound for a class whose verifier is deterministic and uses no randomness, no advice, and no second quantifier.
- Over a fixed finite field, shaving any factor $t^\varepsilon$ off the new deterministic $O_d(st^{d-1})$ constant-degree PIT algorithm, even with a nondeterministic algorithm, resolves Open Problem 1 (an $\Omega(n\log n)$ lower bound) or Open Problem 2 (an $\omega(t\log t)$ arithmetic lower bound); shaving a constant fraction of the exponent for infinitely many degrees separates $\mathrm{VP}_{\math
- Small arithmetic circuits for the permanent or for the universal polynomial give perfectly complete input-oblivious Merlin–Arthur protocols for sparse 3-UNSAT, so ruling out faster protocols translates into arithmetic lower bounds that scale with the protocol's running time (Theorem 6).
- If $\mathrm{PIT}_{\mathbb{Z}}\in\mathrm{NP}$ but $\mathrm{VP}_{\mathbb{Z}}=\mathrm{VNP}_{\mathbb{Z}}$, then for every fixed degree $d$ there is a single-valued FNP construction of degree-$d$ polynomials of optimal circuit complexity $\Theta_d(t^d)$ with coefficients of $O_d(\log t)$ bits (Corollary 7).
- Over any fixed finite field, an analogue of the [KI04] theorem holds without the #P-hardness of the permanent: nondeterministic subexponential-time PIT implies $\mathrm{NEXP}\not\subseteq\mathrm{P/poly}$ or $\mathrm{VP}_{\mathbb{F}}\ne\mathrm{VNP}_{\mathbb{F}}$ (Theorem 8).
Reading between the lines
- My reading, not the paper's: the threshold in Theorem 3—any polynomial-factor saving, even nondeterministic, suffices—turns the two open problems into a concrete algorithmic target, namely shaving a factor of $t$ off the trivial $O_d(st^d)$ coefficient computation for constant-degree PIT over a fixed finite field.
- My inference: the coefficient-boundedness condition inside Theorem 5 suggests that over the integers the real obstacle is keeping intermediate integers short, and the constant-free, bounded-formal-degree model is exactly the regime where identity testing and short coefficients are guaranteed at the same time.
- My inference: the paper's own observation that general circuit gates lack a low-degree verification recurrence—the reason circuits must first be depth-reduced to formulas and branching programs—marks the natural next step: a direct low-degree identity check for product gates would remove the branching-program detour.
- My inference: if Theorem 5's algorithm is confirmed by an independent implementation, the sum-of-squares-plus-block-splitting scheme is a candidate general template for unconditional white-box PIT speedups over the integers in other structured circuit classes that admit a heavy-gate decomposition.
Original abstract
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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | result 0.93 | 0.96 | 0.93 | asserted 1.00 |
| s1 | The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. | interpretation 0.94 | 0.41 | 0.09 | asserted 0.99 |
| s2 | 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). | contribution 0.86 | 0.88 | 0.04 | asserted 1.00 |
| s3 | We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. | contribution 0.64 | 0.92 | 0.05 | asserted 1.00 |
| s4 | 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. | contribution 0.49 | 0.94 | 0.03 | asserted 1.00 |
| s5 | 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}}$. | result 0.91 | 0.91 | 0.05 | asserted 1.00 |
| s6 | 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}}$. | result 0.92 | 0.83 | 0.04 | asserted 0.95 |
| s7 | 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. | contribution 0.53 | 0.96 | 0.25 | asserted 1.00 |
| s8 | 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. | result 0.68 | 0.94 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.