Update on Polynomial Identity Testing
by Amir Shpilka.
Oded's comments
The most striking fact I learned is that the general case
of PIT reduces to the case of depth four.
The original abstract
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 I will present what I find to be the most accessible
important open questions in the field.
Back to
list of Oded's choices.