Shallow Circuits with High-Powered Inputs
Résumé
A polynomial identity testing algorithm must determine whether an input polynomial (given for instance by an arithmetic circuit) is identically equal to 0. In this paper, we show that a deterministic black-box identity testing algorithm for (high-degree) univariate polynomials would imply a lower bound on the arithmetic complexity of the permanent. The lower bounds that are known to follow from derandomization of (low-degree) multivariate identity testing are weaker. To obtain our lower bound it would be sufficient to derandomize identity testing for polynomials of a very specific norm: sums of products of sparse polynomials with sparse coefficients. This observation leads to new versions of the Shub-Smale tau-conjecture on integer roots of univariate polynomials. In particular, we show that a lower bound for the permanent would follow if one could give a good enough bound on the number of real roots of sums of products of sparse polynomials (Descartes' rule of signs gives such a bound for sparse polynomials and products thereof). In their paper on the ``chasm at depth four'', Agrawal and Vinay have shown that low degree multivariate polynomials which have nontrivial arithmetic circuits also have nontrivial arithmetic circuits of depth four. In this second version of our paper we state (and to some extent use) a new result on reduction to depth four for arithmetic circuits.
Origine : Fichiers produits par l'(les) auteur(s)