The Indentity Testing Problem

SHORT TALKS BY POSTDOCTORAL MEMBERS
Topic:	The Indentity Testing Problem
Speaker:	Neeraj Kayal
Affiliation:	Indian Institute of Technology and Member, School of Mathematics
Date:	Wednesday, October 11
Time/Room:	4:00pm - 5:00pm/S-101

---

Identity Testing is the following problem: given an arithmetic circuit C with coefficients from some field F, determine if the polynomial computed by the circuit is the identically zero polynomial or not. This problem admits a simple and efficient randomized polynomial-time algorithm but no deterministic polynomial-time algorithm is known.

In this talk, we will give a quick survey of the problem, its significance, the available algorithms and related open problems.