Testing whether a Multivariate Polynomial is Zero

Pranab Sen School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhaba Road
Tuesday, 16 Jun 2009 (all day)
Suppose we have a polynomial $P$ in variables $X_1, \\ldots, X_n$ with coefficients from a field $F$, with total degree at most $d$. The polynomial $P$ is given in terms of some algebraic expression involving $X_1, \\ldots, X_n$. We want to know if $P$ is identically zero, without opening up the expression in its full glory. For example, we want to know if $(X_1+X_2)(X_1-X_2) - X_12 + X_22$ is
identically zero, without opening up the expression. This problem is known as {\\em polynomial identity testing}, and is an important problem in algorithmic algebra and theoretical computer science.

In this talk, we shall see some efficient methods for this problem. Starting from Schwartz and Zippel's method that uses a generalisation to multivariate polynomials of the well known fact that a non-zero univariate polyomial of degree $d$ has at most $d$ roots, we shall glimpse recent approaches by Chen and Kao that involve transcendental extensions of $F$, Lewin and Vadhan that use the power series ring over $F$, and finally, Agrawal and Biswas's elementary but powerful approach using Chinese remaindering. The last work was the precursor to Agrawal, Kayal and Saxena's famous efficient algorithm for primality testing.