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.