Event Entry
What and Who
Identity testing and lower bounds using algebraic independence
Date, Time and Location
Abstract
One particular algorithmic question, the problem of 'polynomial identity testing' (PIT), occupies a pivotal position in the theory of arithmetic circuit complexity. It is the problem of deciding if the output of a given arithmetic circuit is an identically zero polynomial.
In this work, we present a single, common tool to strictly subsume ALL
known cases of (blackbox) PIT that have been hitherto solved using diverse tools and techniques. Our work significantly generalizes the results obtained by Saxena & Seshadhri (STOC 2011), Saraf & Volkovich (STOC 2011), Anderson et al.(CCC 2011) and Beecken et al.(ICALP 2011), and further brings them under one unifying algebraic-geometry theme: algebraic independence of polynomials and the Jacobian.
In addition, using the same Jacobian based approach, we prove exponential lower bounds for the same circuit models for which we give PIT algorithms. Our results reinforce the intimate connection between identity testing and lower bounds by exhibiting a concrete mathematical tool - the Jacobian - that is equally effective in solving both the problems on certain interesting and previously well-investigated (but not well understood) models of computations.
This is a joint work with Manindra Agrawal, Nitin Saxena and Ramprasad
Saptharishi.
Contact