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.

© Copyright 2023, School of Technology and Computer Science | TIFR - All Rights Reserved | Login