Title: Testing if a Polynomial Formula is Identically 0
Speaker: Shubhangi Saraf, MIT
Date: Monday, January 31, 2011 3:30 PM
Location: Hill Center, Room 705 Rutgers University, Busch Campus, Piscataway, NJ
The Polynomial Identity Testing (PIT) problem considers the task of determining if a multivariate polynomial, described by an arithmetic formula that computes it, is identically zero. The goal is to give an efficient (polynomial time) algorithm for this problem. Note that the trivial "multiply and cancel" approach would in general exponentially blow up a compactly represented formula, and hence be extremely inefficient. The problem however is known to admit an efficient *randomized* algorithm.
The problem occupies a central position in computational complexity, due to recent work of Impagliazzo and Kabanets, who show that a *deterministic* solution to this problem would yield formula size lower bounds, and thus resolve some foundational open questions in computational complexity. Consequently PIT is one of the most interesting problems on the boundary of randomized versus deterministic computation.
In this talk I will describe recent work giving a deterministic polynomial time algorithm for identity testing for the class of formulas of depth 3 in a *blackbox* manner (where one is only allowed to evaluate the formula at chosen points, and not look at it explicitly). Obtaining a similar result for formulas of depth four would solve the full identity testing problem for all formulas (Agrawal-Vinay 08)! Our result resolves a question posed by Klivans and Spielman in 2001. The main technical result that I will describe is a structure theorem for depth three formulas that compute the zero polynomial. I will show that under mild assumptions, any such formula is essentially made up of only very few variables. Our proof is based on a new connection to combinatorial geometry, relying in particular on high dimensional versions of the Sylvester-Gallai incidence theorem.