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.