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.