ECCC-Report TR18-035https://eccc.weizmann.ac.il/report/2018/035Comments and Revisions published for TR18-035en-usWed, 21 Feb 2018 15:50:12 +0200
Paper TR18-035
| Bootstrapping variables in algebraic circuits |
Sumanta Ghosh,
Manindra Agrawal,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2018/035We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are composing $c$ logarithms). Thus, hitting-set generator (hsg) manifests a {\em bootstrapping} behavior--- a partial hsg against very few variables can be efficiently grown to a complete hsg.
A boolean analog, or a pseudorandom generator property of this type, is unheard-of.
Our idea is to use the partial hsg and its annihilator polynomial to efficiently bootstrap the hsg exponentially wrt variables. This is repeated $c$ times in an efficient way.
Pushing the envelope further we show that: {\bf (1)} a quadratic-time blackbox PIT for $6913$-variate degree-$s$ size-$s$ polynomials, will lead to a ``near''-complete derandomization of PIT, and {\bf (2)} a blackbox PIT for $n$-variate degree-$s$ size-$s$ circuits in $s^{n^{\delta}}$-time, for $\delta<1/2$, will lead to a ``near''-complete derandomization of PIT (in contrast, $s^n$-time is trivial).
Our second idea is to study depth-$4$ circuits that depend on constantly many variables. We show that a polynomial-time computable, $O(s^{1.49})$-degree hsg for {\em trivariate} depth-$4$ circuits bootstraps to a quasipolynomial time hsg for general poly-degree circuits, and implies a lower bound that is a bit stronger than Kabanets-Impagliazzo (STOC 2003).Wed, 21 Feb 2018 15:50:12 +0200https://eccc.weizmann.ac.il/report/2018/035