Proc Natl Acad Sci U S A 2019 Apr 11;116(17):8107-8118. Epub 2019 Apr 11.

Department of Computer Science & Engineering, Indian Institute of Technology Kanpur, Kanpur 208016, India

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 needs only to consider size-s degree-s circuits that depend on the first [Formula: see text] variables (where c is a constant and composes a logarithm with itself c times). Thus, the hitting-set generator (hsg) manifests a 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 w.r.t. variables. This is repeated c times in an efficient way. Pushing the envelope further we show that () a quadratic-time blackbox PIT for 6,913-variate degree-s size-s polynomials will lead to a "near"-complete derandomization of PIT and () a blackbox PIT for n-variate degree-s size-s circuits in [Formula: see text] time, for [Formula: see text], will lead to a near-complete derandomization of PIT (in contrast, [Formula: see text] 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, [Formula: see text]-degree hsg for trivariate depth-4 circuits bootstraps to a quasipolynomial time hsg for general polydegree circuits and implies a lower bound that is a bit stronger than that of Kabanets and Impagliazzo [Kabanets V, Impagliazzo R (2003) ].

## Download full-text PDF |
Source |
---|---|

http://dx.doi.org/10.1073/pnas.1901272116 | DOI Listing |

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6486749 | PMC |

April 2019

[formula text]

16

circuits depend

12

degree-s size-s

8

will lead

8

depth-4 circuits

8

text] time

8

derandomization pit

8

blackbox pit

8

partial hsg

8

hsg

7

circuits

7

variables

5

pit

5

[formula

5

type unheard

4

lead "near"-complete

4

idea partial

4

polynomials will

4

size-s polynomials

4

circuits [formula

4

Geometric complexity theory V: Efficient algorithms for Noether normalization

Mulmuley et al.

*J Am Math Soc* 2017

Mulmuley et al.

Depth-4 identity testing and Noetherâ€™s normalization lemma

Mukhopadhyay et al.

2016

Mukhopadhyay et al.

2016

Progress on polynomial identity testing

Saxena et al.

*Bull EATCS* 2009

Saxena et al.