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.