Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
event speaker icon
Zeev Dvir (Weizmann Institute of Science)
event date icon
Sunday, 24.02.2008, 11:00
event location icon
Room 337-8 Taub Bld.
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.