The Polynomial Identity Testing Problem
| COMPUTER SCIENCE/DISCRETE MATH, II | |
| Topic: | The Polynomial Identity Testing Problem |
| Speaker: | Neeraj Kayal |
| Affiliation: | Member, School of Mathematics |
| Date: | Tuesday, January 23 |
| Time/Room: | 10:30am - 12:30pm/West Building Lecture Theatre |
Polynomial Identity Testing is the following problem: given an arithmetic circuit C, determine if the polynomial computed by it is the identically zero polynomial. This problem admits a randomized polynomial-time algorithm but no efficient deterministic algorithm is known.
We will review some existing results on this problem and then give an efficient deterministic algorithm for the special case of circuits of depth three (Sum of Product of Sums) having bounded top fanin.
This is joint work with Nitin Saxena.