### Special Talk hosted by Michael Saks, Mathematics, Rutgers University

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

Abstract:
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.