Hardness-randomness tradeoffs for bounded depth arithmetic circuits

Zeev Dvir, Amir Shpilka, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x1,...., xm) that cannot be computed by a depth d arithmetic circuit of small size then there exists an efficient deterministic algorithm to test whether a given depth d - 8 circuit is identically zero or not (assuming the individual degrees of the tested circuit are not too high). In particular, if we are guaranteed that the circuit computes a multilinear polynomial then we can perform the identity test efficiently. To the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. The above results are obtained using the arithmetic Nisan-Wigderson generator of Impagliazzo and Kabanets together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. This theorem deals with polynomial equations of the form P(x 1,..., xn, y) =≡ 0 and shows that if P has a circuit of depth d and size s and if the polynomial f(x1,..., xn) satisfies P(x1,..., xn, f(x1,..., x n)) = 0≡ then f has a circuit of depth d + 3 and size O(s r + mr), where m is the degree of f and r is the highest degree of the variable y appearing in P. In the other direction we observe that the methods of Impagliazzo and Kabanets imply that if we can derandomize polynomial identity testing for bounded depth circuits then NEXP does not have bounded depth arithmetic circuits. That is, either NEXP ⊈ P/poly or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.

Original languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery (ACM)
Pages741-748
Number of pages8
ISBN (Print)9781605580470
DOIs
StatePublished - Jan 1 2008
Externally publishedYes
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada
Duration: May 17 2008May 20 2008

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
CountryCanada
CityVictoria, BC
Period5/17/085/20/08

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Arithmetic circuits
  • Bounded depth circuits
  • Hardness-randomness tradeoffs
  • Identity testing
  • Lower bounds

Fingerprint Dive into the research topics of 'Hardness-randomness tradeoffs for bounded depth arithmetic circuits'. Together they form a unique fingerprint.

Cite this