Blackbox Identity Testing for Depth-3 Circuits

arithmetic circuit is the zero circuit. By definition it is a natural
algebraic problem. Since circuits model computation, a study to
efficiently solve identity testing is really about understanding
computation. It is currently an open problem but there are interesting
connections known to computational complexity lower bounds.

As it is a challenging problem, the current research has focused on
special kinds of circuits. In this talk we will consider depth-3
circuits -- a sum of product of linear polynomials. We will assume
that we are given a depth-3 circuit C(x_1,...,x_n) in the input via a
blackbox, i.e. we could not see C but could evaluate it at points of
our choice. We give a deterministic polynomial time blackbox identity
test for such circuits with bounded top fanin (over any field). This
completely solves an open question of Klivans and Spielman (STOC
2001).

This is joint work with C. Seshadhri, to be presented in STOC 2011.