Algebraic hardness-to-randomness takes a polynomial that is provably or conjecturally hard to compute and turns it into a short list of test points. That list then certifies, deterministically, whether a small arithmetic circuit (a network of addition and multiplication gates) computes the zero polynomial. Every such conversion rests on a reconstruction argument. If the test points fail to catch some nonzero circuit, one builds from that circuit a new small circuit for the hard polynomial, which is a contradiction. Today this step calls on a heavy theorem: polynomial-size circuits are closed under taking factors. As a result, the cost of the conversion is tied to the degree of the failing circuit, to its squarefree part, and to the characteristic of the field. Those dependencies are what keep the known results for bounded-depth circuits at subexponential time and exclude small fields.
Our claim is that reconstruction never needs general factoring. It only needs one simple root, of the form $y = P(z)$, of a circuit that is linear in the unknown at that root. The cost of extracting such a root is exactly the cost Bläser and Jindal pay to recover the "witness" of a symmetric polynomial, about $d^2$ times the circuit size, where $d$ is the degree of the hard polynomial alone. We propose to prove a root-closure lemma that isolates this cost and to build its bounded-depth and positive-characteristic versions. We will then recompute the hardness needed for polynomial-time, quasipolynomial-time and subexponential-time deterministic identity testing. The outcome would show which parts of the factoring machinery the derandomization pipeline actually consumes, and how much hardness that saves.
Core Claim
Let $C(z,y)$ be a circuit of size $s$ with $C(z,P(z)) = 0$ and $\partial_y C(z,P(z)) \neq 0$. Here $z$ is a block of $m$ variables, $y$ is a single variable, and $P$ is a polynomial of degree $d$. Then $P$ is computed by a circuit of size
$$ O(d^2 s), $$
and this bound holds independently of the total degree $D$ of $C$ and of the degree of its squarefree part (the product of its distinct irreducible factors). The form comes from Newton iteration on a simple root, which doubles the number of correct homogeneous components per round. Truncating to degree $d$ costs $O(d)$ per gate across $O(\log d)$ rounds, or $O(d^2)$ with naive homogenization, the same accounting as Theorem 4 of On the Complexity of Symmetric Polynomials. That paper recovers the witness $f$ from $f_{\text{Sym}}$ by treating each $x_i$ as a simple root of the generic univariate polynomial whose coefficients are $e_1,\dots,e_n$, and it obtains $L(f) \le \tilde O(d^2 L(f_{\text{Sym}}) + d^2n^2)$.
This matters because, in the hybrid argument behind design-based generators, the failing circuit has degree roughly $\deg(\text{distinguisher}) \cdot d$. That quantity can be far larger than $d$, and its squarefree part is uncontrolled. Bounds stated through general factor closure therefore pay for $D$ or for the radical degree. The root lemma does not. The remaining work is to make the simple-root hypothesis hold, to carry the lemma into bounded depth, and to see how far it survives in small characteristic.
Research Program
The first component is the root-closure lemma together with its preprocessing step. A hybrid argument may yield $C'$ with $(y-P)^k$ dividing it for some $k>1$. Over characteristic zero, or when $k<p$, differentiating $k-1$ times in $y$ produces a simple root at a cost of a factor of $k$ (more precisely, of $\min(k, \deg_y C')$). We will prove the lemma in this form and compare it carefully against three existing closure results, each of which supplies part of the method:
- Closure of VP under taking factors: a short and simple proof proves closure of VP, the class of polynomial-size circuits, using Newton iteration with a Sylvester-matrix Jacobian, but the argument is existential.
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring handles all roots at once, including repeated ones, through all-roots Newton iteration, and pays for the degree of the radical.
- Some Closure Results for Polynomial Factorization and Applications proves closure of VNP and gives bounded-depth closure for factors of degree up to $\log^a n$.
Our lemma reuses the Newton step common to all three. It deliberately gives up general factors, multiple roots of high multiplicity, and the radical parameter, and in exchange obtains independence from $D$. The lemma is constructive by design, which addresses the gap between the existential Sylvester proof and the explicit generators that derandomization requires.
The second component is the bounded-depth version, which is where the payoff is largest. Some Closure Results for Polynomial Factorization and Applications turns lower bounds for bounded-depth circuits on low-degree explicit polynomials into deterministic subexponential identity testing. Its restriction to factors of degree $\log^a n$ is the stated open barrier. With the root lemma, the reconstructed circuit has size $O(d^2 s)$ and degree $d$. Standard depth reduction of such a circuit to depth $k$ costs a factor governed by $d$ alone, not by the degree of the distinguisher.
We will derive the exact trade-off curve: for which pairs (degree $d$ of the hard polynomial, bounded-depth lower bound $T(d)$) the reconstructed circuit stays below $T(d)$. This yields a conversion that accepts hard polynomials of degree polynomial in $n$, not just polylogarithmic, as long as the assumed lower bound beats the depth-reduction cost. We will state precisely which lower-bound shapes suffice for quasipolynomial time and which for polynomial time. The aim is to replace the low-degree hypothesis with a quantitative one, not to remove hardness assumptions.
The third component is positive characteristic. Newton iteration for a simple root divides only by $\partial_y C$ evaluated at the root and never by factorials, so the lemma itself should hold over every field, including $\mathbb{F}_2$. The breakdown that all three closure papers and the symmetric-witness paper note in small characteristic enters only through multiplicity reduction. When $p$ divides $k$, the root lemma does not apply directly. We will study the extreme case $(y-P)^{p} = y^p - P^p$, where the hybrid circuit yields a circuit for $P^p$. Over $\mathbb{F}_p$, $P^p$ equals $P$ with coefficients raised to the $p$-th power, evaluated at $z^p$. We ask when hardness of $P$ transfers to hardness of this Frobenius twist. If it does, identity testing via design generators extends to small fields for the hard families used in practice.
The fourth component uses witness complexity to choose and audit hard families. Corollary 21 of On the Complexity of Symmetric Polynomials shows that symmetrizing a VNP-complete family keeps it VNP-complete. VNP is the algebraic analogue of NP. Theorem 4 of the same paper bounds how much hardness can be lost going from $f$ to $f_{\text{Sym}}$. We will check whether symmetrized hard polynomials make cheaper generators. Their reconstruction can use the universal root-finding for $T^n - e_1T^{n-1} + \dots$, whose truncated power series have known closed forms. That may give smaller constants or lower depth in the bounded-depth trade-off. This component is exploratory. If symmetric families offer no advantage beyond the $d^2$ loss already accounted for, we will report that as a finding.
The Boolean uses of elementary symmetric polynomials stay context only. Better Pseudorandom Generators from Milder Pseudorandom Restrictions decomposes bias functions through Newton–Girard identities to fool read-once formulas, and Improved Pseudorandom Generators for AC0 Circuits brings constant-depth Boolean generators within a $\log\log m$ factor of optimal. Both live on the Boolean cube and use symmetric polynomials in the analysis, not in the reconstruction. The proposal does not claim to touch Boolean generators.
Baselines
The naive reference point is randomized identity testing by evaluation at random points. Its randomness cost is shown to be suboptimal by a constant factor when $d \ll n$ in Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness. That paper also gives the strongest randomized baseline: Sidon-set reductions combined with subfield testers use $d \log n + \log(1/\epsilon) + O(d\log\log n)$ random bits, matching the information-theoretic minimum. Our deterministic generators do not compete with this on random bits. The fair comparison is the following: on the same circuit families and degrees, the logarithm of our hitting-set size should approach this randomness count from above. Matching it within a constant factor for any non-sparse bounded-depth class under a stated hardness assumption would count as success.
The strongest existing deterministic conversion is the bounded-depth hardness-to-randomness theorem of Some Closure Results for Polynomial Factorization and Applications. It reaches subexponential deterministic identity testing from superpolynomial lower bounds for low-degree polynomials. The comparison will hold the hard polynomial, the design, and the depth fixed and vary only the reconstruction step. We beat it if, for the same lower-bound hypothesis, we either admit hard polynomials of degree above $\log^a n$ or reach a strictly smaller running-time class. For orientation on the other route to polynomial time, A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization obtains blackbox identity testing in P from sum-of-cubes hardness, where the polynomial is written as a sum of cubes of simpler polynomials. We compare against it by the strength of the assumptions, not by any numerical figure.
The ablation that isolates our key ingredient replaces the root lemma with general factor closure inside the same hybrid argument. We use the radical-degree bound of Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring. Any improvement must disappear under this swap. If it does not, the gain comes from somewhere other than the root lemma.
Why not just…?
Why not just use the existing factor-closure theorems directly? They prove much more than reconstruction needs, and they charge for it. The radical-degree bound of Discovering the Roots is excellent when the radical is small, but the hybrid circuit is arbitrary and its radical can have degree near $D$. The bounded-depth result of Some Closure Results is explicitly limited to factors of polylogarithmic degree. The ablation above tests directly whether the specialization buys anything. A skeptic might say the root lemma is folklore. Its Newton step certainly is, and we take it from these papers. What we contribute is the degree-of-$P$-only accounting carried through bounded depth and positive characteristic, together with the resulting hardness thresholds.
Why not just test identities with random evaluation, or with optimal-randomness testers? Those methods are randomized. Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness settles the randomness question but says nothing about deterministic testing. We use it as the yardstick our hitting-set sizes should approach, not as a competitor that answers the same question.
Why not just pursue the sum-of-cubes route to deterministic polynomial time? It is a real alternative, and it reaches P. It does so, however, under a hardness hypothesis that is not known to follow from the bounded-depth lower bounds our route consumes, and it inflates the variable count through multilinearization (A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization). We will report whether our bounded-depth thresholds are implied by, imply, or are incomparable with sum-of-cubes hardness. If they turn out to be implied, the bounded-depth component loses its motivation and we will say so.
Decisive Checks
The first check is computational and falsifiable. We will implement the root lemma, and for comparison general factoring, in a computer algebra system. The generated circuits will satisfy $C(z,P(z))=0$ with $\deg P$ fixed and the total degree $D$ swept over several orders of magnitude, over $\mathbb{Q}$, over $\mathbb{F}_p$ with $p > d$, and over $\mathbb{F}_2$. The lemma predicts that the reconstructed circuit size stays flat in $D$ and grows like $d^2 s$. General factoring should grow with the radical degree. Measured growth in $D$ for the simple-root case would refute the core claim.
A second check targets small characteristic. Over $\mathbb{F}_2$ and $\mathbb{F}_3$, we will build hybrid circuits with root multiplicity divisible by $p$ and test whether the Frobenius-twist recovery yields circuits for the twisted version of $P$ of the predicted size.
Third, we will build design-based hitting sets from symmetrized and unsymmetrized hard candidates, such as the symmetrized permanent of small dimension. We then exhaustively check them against all nonzero circuits of very small size and depth. The check is whether either family fails, and whether symmetrization changes the constants in the reconstruction.
There are no empirical benchmarks for this question: no reported result found on Lacuna for hitting-set size on concrete bounded-depth circuit families. The reference numbers are the theoretical bounds quoted above, chiefly $L(f) \le \tilde O(d^2L(f_{\text{Sym}})+d^2n^2)$ and $d\log n+\log(1/\epsilon)+O(d\log\log n)$ random bits.
The final theoretical check is the trade-off curve itself. The project succeeds if it produces a stated lower-bound shape for bounded-depth circuits on polynomials of degree $n^{\Omega(1)}$ that provably yields deterministic identity testing faster than the subexponential conversion of Some Closure Results.
References
- On the Complexity of Symmetric Polynomials
- Closure of VP under taking factors: a short and simple proof
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- Some Closure Results for Polynomial Factorization and Applications
- Better Pseudorandom Generators from Milder Pseudorandom Restrictions
- Improved Pseudorandom Generators for AC0 Circuits
- Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness
- A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization