Arithmetic circuits: the chasm at depth four gets wider

Abstract : In their paper on the ''chasm at depth four'', Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size 2^o(m) also admit arithmetic circuits of depth four and size 2^o(m). This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case. In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of n*n matrices has circuits of size polynomial in n, then it also has depth 4 circuits of size n^O(sqrt(n)*log(n)). Our depth four circuits use integer constants of polynomial size. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also give an application to boolean circuit complexity, and a simple (but suboptimal) reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree.
Type de document :
Pré-publication, Document de travail
2012
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00494642
Contributeur : Pascal Koiran <>
Soumis le : jeudi 22 mars 2012 - 16:38:31
Dernière modification le : mardi 24 avril 2018 - 13:52:19
Document(s) archivé(s) le : samedi 23 juin 2012 - 02:40:23

Fichiers

depth4.revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00494642, version 4
  • ARXIV : 1006.4700

Collections

Citation

Pascal Koiran. Arithmetic circuits: the chasm at depth four gets wider. 2012. 〈ensl-00494642v4〉

Partager

Métriques

Consultations de la notice

98

Téléchargements de fichiers

113