Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-121 | 21st November 2007 00:00

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits


Authors: Zeev Dvir, Amir Shpilka, Amir Yehudayoff
Publication: 7th December 2007 11:34
Downloads: 1144


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(x_1,...,x_m) 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 tested 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 the arithmetic Nisan-Wigderson generator of [KabanetsImpagliazzo04] 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,...,x_n,y) \equiv 0 and shows that if P has a circuit of depth d and size s and if the polynomial f(x_1,...,x_n) satisfies P(x_1,...,x_n,f(x_1,...,x_n)) \equiv 0 then f has a circuit of depth d+3 and size O(s*r + m^r), where m is the total degree of f and r is the degree of y in P.

In the other direction we observe that the methods of [KabanetsImpagliazzo04] 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 \not \subseteq P/poly$ or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.

ISSN 1433-8092 | Imprint