Title: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
Speaker: Amir Yehudayoff, The Weizmann Institute of Science
Date: Wednesday, October 1, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Kabanets and Impagliazzo showed a tight connection between proving lower bounds and solving the polynomial identity test problem without using randomness. We will discuss an analog of their result for constant depth circuits. The proof we shall discuss follows the ideas of Kabanets and Impagliazzo, except one part for which we need to establish a new theorem about `roots of polynomial equations in constant depth'. We will mainly focus on this new theorem.
This is joint work with Zeev Dvir and Amir Shpilka.