Theory of Computing
-------------------
Title     : Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
Authors   : Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse
Volume    : 19
Number    : 12
Pages     : 1-30
URL       : https://theoryofcomputing.org/articles/v019a012

Abstract
--------
$ \newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\inparen}[1]{\left( #1 \right)}
\newcommand{\F}{\mathbb{F}} $

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 $|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."

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 - \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.


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


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