pdf icon
Volume 19 (2023) Article 12 pp. 1-30
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
Received: April 16, 2019
Revised: August 5, 2021
Published: December 31, 2023
Download article from ToC site:
[PDF (437K)] [PS (2142K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
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]

$ \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 $\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.”
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).