SPEAKER: Moritz Hardt TIME: Wednesday 12-1pm, April 25, 2007 PLACE: NSH 1507 TITLE: Arithmetic Circuit Identity Testing for Sparse Polynomials ABSTRACT: We give a deterministic identity test for multivariate polynomials represented by arithmetic circuits. The runtime of our algorithm is polynomial in s and m, where s is the size of the circuit and m the number of monomials of the given polynomial. Our technique applies to arbitrary polynomial rings. We can improve the runtime significantly with few random bits.