Bootstrapping variables in algebraic circuits.

Authors:
Sumanta Ghosh
Sumanta Ghosh
Protein Folding and Dynamics Laboratory

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.1901272116DOI Listing
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6486749PMC
April 2019

Publication Analysis

Top Keywords

[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

Altmetric Statistics

References

(Supplied by CrossRef)
A probabilistic remark on algebraic program testing
Demillo et al.
Inf Process Lett 1978
Depth-4 identity testing and Noether’s normalization lemma
Mukhopadhyay et al.
2016
Progress on polynomial identity testing
Saxena et al.
Bull EATCS 2009

Similar Publications