Blackbox Polynomial Identity Testing for Depth 3 Circuits

Testing to see if a Boolean circuit computes the identically zero function is a fundamental problem in computational complexity.
Known as the SAT (for satisfiability) problem, it is the first NP-complete problem, and a polynomial time algorithm for this problem would show P=NP.
The algebraic analog of this problem, which attempts to determine if an arithmetic circuit (whose inputs are integers, and gates add or multiply their inputs) computes the identically zero function turns to be an equally interesting problem.
Every gate of such a circuit computes a polynomial in the input variables and so the goal here is to test if the output polynomial is the identically zero function, leading to this problem being known as the Polynomial Identity Testing problem (PIT).

Unlike SAT, PIT does have fast randomized solutions: Just pick random values for the input variables and the output is very unlikely to be zero if the polynomial is not identically zero. However a deterministic solution to this problem is not known and, as recent work by Impagliazzo and Kabanets, and Agrawal and Vinay have shown, such solutions have major implications for both complexity theory and algorithm design. A complete derandomization of PIT would imply superpolynomial circuit lower bounds, one of the major quests of complexity theory. In addition, special cases of PIT play an important role in algorithmic problems like primality testing and perfect matching.

In this talk I will describe a recent work giving a deterministic polynomial time algorithm for blackbox identity testing for depth three circuits with bounded top fanin. Obtaining a similar result for general circuits of depth 4 would essentially derandomize identity testing for general circuits (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 3 circuits that compute the zero polynomial. I will show that under mild assumptions, any such circuit is essentially made up of only constantly many variables. This proves a conjecture of Dvir and Shpilka from 2005. Our blackbox identity test follows from this structure theorem by combining it with a construction of Karnin and Shpilka.

Speaker Details

Shubhangi is a third year PhD student in the EECS department and theory of computation group at MIT, advised by Madhu Sudan. Prior to this, she did her undergrad in the mathematics department, also at MIT. She also spent a year as a math exchange student at the University of Cambridge, UK. She is interested in problems in computational complexity and pseudorandomness.

Date:
Speakers:
Shubhangi Saraf
Affiliation:
MIT