Shallow Circuits with High-Powered Inputs

Abstract : 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 this third version of our paper we show that the same lower bound would follow even if one could only prove a slightly superpolynomial upper bound on the number of real roots. This is a consequence of a new result on reduction to depth 4 for arithmetic circuits which we establish in a companion paper. We also show that an even weaker bound on the number of real roots would suffice to obtain a lower bound on the size of depth 4 circuits computing the permanent.
Type de document :
Pré-publication, Document de travail
A few typos corrected. 2010
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger
Contributeur : Pascal Koiran <>
Soumis le : jeudi 29 juillet 2010 - 22:52:01
Dernière modification le : jeudi 8 février 2018 - 11:09:25
Document(s) archivé(s) le : jeudi 4 novembre 2010 - 10:40:39


Fichiers produits par l'(les) auteur(s)


  • HAL Id : ensl-00477023, version 4
  • ARXIV : 1004.4960



Pascal Koiran. Shallow Circuits with High-Powered Inputs. A few typos corrected. 2010. 〈ensl-00477023v4〉



Consultations de la notice


Téléchargements de fichiers