Recent Results on Polynomial Identity Testing
Speaker: Amir Shpilka , Technion
Date: November 16 2010
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: Polynomial Identity Testing (PIT for short) is the problem of
efficiently and deterministically deciding whether a given (explicitly
or via black-box access) arithmetic circuit computes the zero
polynomial. This is one of the most fundamental problems in
computational complexity and it is strongly related to the problem of
proving lower bounds for arithmetic circuits. In this talk I will
survey several results on the PIT problem. Specifically I will discuss
the relation between derandomization of PIT and circuit lower bounds,
explain the importance of derandomizing PIT in the bounded depth model
and give an overview of the ideas behind several recent detrerministic
PIT algorithms, designed for restricted circuit classes. At the end of
the talk, time permitting, I will present what I find to be the most
accessible important open questions in the field.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in November 2010
