### DIMACS Theoretical Computer Science Seminar

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.