TR18-035 Authors: Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

Publication: 21st February 2018 15:50

Downloads: 279

Keywords:

We 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).