Speaker:
Time:
Venue:
- AG-69
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.