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.