Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2018
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908157073162240 |
|---|---|
| author | Kumar, Mrinal Saptharishi, Ramprasad Tengse, Anamay |
| author_facet | Kumar, Mrinal Saptharishi, Ramprasad Tengse, Anamay |
| contents | $ \newcommand{\inparen}[1]{\left( #1 \right)} \newcommand{\pfrac}[2]{\inparen{\frac{1}{2}}} \newcommand{\ilog}[1]{\log^{\circ #1}} \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:
$\bullet$ Let $ε> 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-ε}$ 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^{Ω(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 $δ> 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1807_06323 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models Kumar, Mrinal Saptharishi, Ramprasad Tengse, Anamay Computational Complexity 68W30, 68Q87, 68Q06 F.2.1; F.1.3 $ \newcommand{\inparen}[1]{\left( #1 \right)} \newcommand{\pfrac}[2]{\inparen{\frac{1}{2}}} \newcommand{\ilog}[1]{\log^{\circ #1}} \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: $\bullet$ Let $ε> 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-ε}$ 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^{Ω(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 $δ> 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. |
| title | Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models |
| topic | Computational Complexity 68W30, 68Q87, 68Q06 F.2.1; F.1.3 |
| url | https://arxiv.org/abs/1807.06323 |