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.