23
Apr
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.
