Zeev Dvir (Weizmann Institute of Science)
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. 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.
Joint work with Amir Shpilka and Amir Yehudayoff.