Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #2 to TR18-132 | 4th September 2018 22:31

Near-optimal Bootstrapping of Hitting Sets for Algebraic Models

Revision #2
Authors: Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse
Accepted on: 4th September 2018 22:31
Keywords:

Abstract:

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel [Ore22,DL78,Zip79,Sch80] 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 a grid $S^n \subseteq \mathbb{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 $s$, we have an explicit hitting set of size $s^{\exp \circ \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 compared to the trivial $(s+1)^{n}$ sized 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 [AGS18] who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most $(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 branching programs and formulas.

Changes to previous version:

The statement of the main result has been strengthened significantly compared to the original version. Additionally, the new result also works for algebraic branching programs and formulas.
A more detailed analysis of the bootstrapping procedure has also been added to the appendix.

Revision #1 to TR18-132 | 2nd September 2018 21:54

Near-optimal Bootstrapping of Hitting Sets for Algebraic Models

Revision #1
Authors: Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse
Accepted on: 2nd September 2018 21:54
Keywords:

Abstract:

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel [Ore22,DL78,Zip79,Sch80] 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 a grid $S^n \subseteq \mathbb{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 any constant $\epsilon > 0$) for the class of $n$-variate degree $s$ polynomials that are computable by algebraic circuits of size $s$, then for all $s$, we have an explicit hitting set of size $s^{\exp \circ \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 compared to the trivial $(s+1)^{n}$ sized 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 [AGS18] who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most $(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 branching programs and formulas.

Changes to previous version:

The main theorem of the paper has been strengthened significantly. Additionally, the stronger theorem holds even for subclasses of algebraic circuits, such as algebraic formulas and algebraic branching programs.

Paper:

TR18-132 | 17th July 2018 12:56

Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

TR18-132
Authors: Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse
Publication: 22nd July 2018 16:05
The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel 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 a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ algebraic circuits in $n$ variables that runs in time $\mathrm{poly}(s) \cdot (s+1)^n$.
In a surprising recent result, Agrawal, Ghosh and Saxena (STOC 2018) showed any deterministic blackbox PIT algorithm for degree-$s$, size-$s$, $n$-variate circuits with running time as bad as $s^{n^{0.5 - \delta}}\mathrm{Huge}(n)$, where $\delta > 0$ and $\mathrm{Huge}(n)$ is an arbitrary function, can be used to construct blackbox PIT algorithms for degree-$s$ size $s$ circuits with running time $s^{\exp \circ \exp (O(\log ^\ast s))}$.
The authors asked if a similar conclusion followed if their hypothesis was weakened to having deterministic PIT with running time $s^{o(n)}\cdot \mathrm{Huge}(n)$. In this paper, we answer their question in the affirmative. We show that, given a deterministic blackbox PIT that runs in time $s^{o(n)}\cdot \mathrm{Huge}(n)$ for all degree-$s$ size-$s$ algebraic circuits over $n$ variables, we can obtain a deterministic blackbox PIT that runs in time $s^{\exp \circ \exp(O(\log^{*}s))}$ for all degree-$s$ size-$s$ algebraic circuits over $n$ variables. In other words, any blackbox PIT with just a slightly non-trivial exponent of $s$ compared to the trivial $s^{O(n)}$ test can be used to give a nearly polynomial time blackbox PIT algorithm.