Campus Event Calendar

Event Entry

What and Who

Identity testing and lower bounds using algebraic independence

Chandan Saha
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Friday, 11 May 2012
30 Minutes
E1 4


A polynomial in many variables, when written down verbosely as a sum of monomials, might have a humongous expression. Arithmetic circuits, on the other hand, provide a succinct way to represent multivariate polynomials. An arithmetic circuit, consisting of addition and multiplication gates, takes several variables as input and outputs a polynomial in those variables. The study of arithmetic circuits - as to which algorithmic questions on polynomials can be resolved efficiently in this model of computation, and which polynomials do not admit any polynomial-sized circuit representation (lower bounds) - form the foundation of algebraic complexity theory.

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


Chandan Saha
--email hidden
passcode not visible
logged in users only

Chandan Saha, 05/09/2012 11:58 -- Created document.