Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models

Abstract

The Polynomial Identity Lemma (also called the "Schwartz--Zippel lemma") states that any nonzero polynomial $f(x_1,\dots ,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 $|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: $\bullet$ Let $\hat{I}\mu >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-\hat{I}\mu }$ 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^{\hat{I}\text{c◯}(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. $\bullet$ 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 $\inparen{s^{n^{0.5 - δ}}}$ (where $\hat{I}´>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.

Published in Theory of Computing, Volume 19 (2023), Article 12; Received: April 16, 2019, Revised: August 5, 2021, Published: December 31, 2023