Revised: August 5, 2021

Published: December 31, 2023

**Keywords:**algebraic circuits, polynomial identity testing, derandomization, hardness-randomness, bootstrapping

**Categories:**complexity, circuit complexity, algebraic circuits, polynomial identity testing, derandomization, hitting set, hardness vs. randomness

**ACM Classification:**F.2.1, F.1.3

**AMS Classification:**68W30, 68Q87, 68Q06

**Abstract:**
[Plain Text Version]

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
any
grid $S^n \subseteq \F^n$ with $\abs{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 large $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^{\Omega(1)} $ improvement) compared to the trivial $(s+1)^{n}$-size 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.”

----------------------------

A preliminary version of this paper appeared in the Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).