The polynomial identity lemma (also called the ``Schwartz-Zippel lemma'') states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \F^n$ with $|S| > s$. Thus, there is an explicit hitting set for all $n$-variate degree $s$, size $s$ algebraic circuits of size $(s+1)^n$.

In this paper, we prove the following results:

1. Let $\varepsilon > 0$ be a constant. For a sufficiently large constant $n$ and all $s > n$, if we have an explicit hitting set of size $(s+1)^{n-\varepsilon}$ for the class of $n$-variate degree $s$ polynomials that are computable by algebraic circuits of size $s$, then for all $s$, we have an explicit hitting set of size $s^{\exp(\exp (O(\log^\ast s)))}$ for $s$-variate circuits of degree $s$ and size $s$.

That is, if we can obtain a barely non-trivial exponent (a factor-$s^{O(1)} $ improvement) compared to the trivial $(s+1)^{n}$ sized hitting set even for constant variate circuits, we can get an almost complete derandomization of PIT.

2. The above result holds when ``circuits'' are replaced by ``formulas'' or ``algebraic branching programs''.

This extends a recent surprising result of Agrawal, Ghosh and Saxena~(STOC 2018, PNAS 2019) who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most $(s^{n^{0.5 - \delta}})$ (where $\delta>0$ is any constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh and Saxena to only require a slightly non-trivial saving over the trivial hitting set, and also presents the first such result for algebraic formulas.

Accepted for publication ToC.
A new section has been added that derives a bootstrapping result from a different hypothesis: e.g. when the number of variables grows with the size.

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel [Ore22,DL78,Zip79,Sch80] states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is an explicit hitting set for all $n$-variate degree $s$, size $s$ algebraic circuits of size $(s+1)^n$.

In this paper, we prove the following results:

- Let $\epsilon > 0$ be a constant. For a sufficiently large constant $n$ and all $s > n$, if we have an explicit hitting set of size $(s+1)^{n-\epsilon}$ for the class of $n$-variate degree $s$ polynomials that are computable by algebraic circuits of size $s$, then for all $s$, we have an explicit hitting set of size $s^{\exp \circ \exp (O(\log^\ast s))}$ for $s$-variate circuits of degree $s$ and size $s$.
That is, if we can obtain a barely non-trivial exponent compared to the trivial $(s+1)^{n}$ sized hitting set even for constant variate circuits, we can get an almost complete derandomization of PIT.

- The above result holds when "circuits" are replaced by "formulas" or "algebraic branching programs".

This extends a recent surprising result of Agrawal, Ghosh and Saxena [AGS18] who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most $(s^{n^{0.5 - \delta}})$ (where $\delta>0$ is any constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh and Saxena to only require a slightly non-trivial saving over the trivial hitting set, and also presents the first such result for algebraic branching programs and formulas.

The statement of the main result has been strengthened significantly compared to the original version. Additionally, the new result also works for algebraic branching programs and formulas.
A more detailed analysis of the bootstrapping procedure has also been added to the appendix.

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel [Ore22,DL78,Zip79,Sch80] states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is an explicit hitting set for all $n$-variate degree $s$, size $s$ algebraic circuits of size $(s+1)^n$.

In this paper, we prove the following results:

- Let $\epsilon > 0$ be a constant. For a sufficiently large constant $n$ and all $s > n$, if we have an explicit hitting set of size $(s+1)^{n-\epsilon}$ (for any constant $\epsilon > 0$) for the class of $n$-variate degree $s$ polynomials that are computable by algebraic circuits of size $s$, then for all $s$, we have an explicit hitting set of size $s^{\exp \circ \exp (O(\log^\ast s))}$ for $s$-variate circuits of degree $s$ and size $s$.
That is, if we can obtain a barely non-trivial exponent compared to the trivial $(s+1)^{n}$ sized hitting set even for constant variate circuits, we can get an almost complete derandomization of PIT.

- The above result holds when "circuits" are replaced by "formulas" or "algebraic branching programs".

This extends a recent surprising result of Agrawal, Ghosh and Saxena [AGS18] who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most $(s^{n^{0.5 - \delta}})$ (where $\delta>0$ is any constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh and Saxena to only require a slightly non-trivial saving over the trivial hitting set, and also presents the first such result for algebraic branching programs and formulas.

The main theorem of the paper has been strengthened significantly. Additionally, the stronger theorem holds even for subclasses of algebraic circuits, such as algebraic formulas and algebraic branching programs.

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ algebraic circuits in $n$ variables that runs in time $\mathrm{poly}(s) \cdot (s+1)^n$.
In a surprising recent result, Agrawal, Ghosh and Saxena (STOC 2018) showed any deterministic blackbox PIT algorithm for degree-$s$, size-$s$, $n$-variate circuits with running time as bad as $s^{n^{0.5 - \delta}}\mathrm{Huge}(n)$, where $\delta > 0$ and $\mathrm{Huge}(n)$ is an arbitrary function, can be used to construct blackbox PIT algorithms for degree-$s$ size $s$ circuits with running time $s^{\exp \circ \exp (O(\log ^\ast s))}$.

The authors asked if a similar conclusion followed if their hypothesis was weakened to having deterministic PIT with running time $s^{o(n)}\cdot \mathrm{Huge}(n)$. In this paper, we answer their question in the affirmative. We show that, given a deterministic blackbox PIT that runs in time $s^{o(n)}\cdot \mathrm{Huge}(n)$ for all degree-$s$ size-$s$ algebraic circuits over $n$ variables, we can obtain a deterministic blackbox PIT that runs in time $s^{\exp \circ \exp(O(\log^{*}s))}$ for all degree-$s$ size-$s$ algebraic circuits over $n$ variables. In other words, any blackbox PIT with just a slightly non-trivial exponent of $s$ compared to the trivial $s^{O(n)}$ test can be used to give a nearly polynomial time blackbox PIT algorithm.