Computer Science/Discrete Mathematics Seminar I

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 con gurations of linear forms appearing in any high rank circuit that prevent it from being identically zero. (Joint work with Neeraj Kayal)