On Monday, May 17, 2010
Shubhangi Saraf (M.I.T.) will speak on
Blackbox Polynomial Identity Testing for Depth 3 Circuits

Abstract:
I will talk about a recent work describing a deterministic polynomial time
algorithm for blackbox identity testing for depth three circuits with bounded
top fanin over the field of rational numbers. This resolves a question posed by
Klivans and Spielman (STOC 2001). The main technical result that I will
describe is a structure theorem for depth three circuits with bounded top fanin
that compute the zero polynomial. We show that any such circuit (with mild
additional conditions) must have small `rank' (where the rank of a depth 3
circuit is the dimension of the span of the linear forms computed by the
circuit). This proves a weak form of a conjecture of Dvir and Shpilka (STOC
2005). Our blackbox identity test follows from this structure theorem by
combining it with a construction of Karnin and Shpilka (CCC 2008).

Our proof of the structure theorem exploits the geometry of finite point sets
in $R^n$. We identify the linear forms appearing in the circuit $C$ with points
in $R^n$. We then invoke a high dimensional version of the Sylvester-Gallai
Theorem, a theorem from incidence geometry, that enables us to identify certain
configurations of linear forms appearing in any high rank circuit that prevent
it from being identically zero. (Joint work with Neeraj Kayal)