Computer Science/Discrete Mathematics Seminar II

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.