Tata Institute of Fundamental Research
Testing whether a Multivariate Polynomial is Zero
Seminar
Speaker:
Pranab Sen
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhaba Road
Date:
Tuesday, 16 Jun 2009 (all day)
Venue:
AG-69
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Pranab Sen School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhaba Road |
| Date: | Tuesday, 16 Jun 2009 (all day) |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
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.
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.