Haifa University - Dept. of CS Theory Seminar
Speaker : Zeev Dvir, Weizmann.
Title: "Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits".
Date: Thursday, Mar. 13.
Place: Haifa U. Education Building, room 570.
Time: 12:15 - 13:30
Abstract:
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.