Bibliographic Information: Appeared in Proceedings of the 33rd Symposium on Theory of Computing (STOC), 2001
We present a randomized polynomial time algorithm to determine if a
multivariate polynomial is zero using $O(\log mn\delta)$ random bits
where $n$ is the number of variables, $m$ is the number of monomials,
and $\delta$ is the total degree of the unknown polynomial. All other
known randomized identity tests use $\Omega(n)$ random bits even when the
polynomial is sparse and has low total degree. In such cases our
algorithm has an exponential savings in randomness. In addition, we
obtain the first polynomial time algorithm for interpolating sparse
polynomials over finite fields of large characteristic. Our approach
uses an error correcting code combined with the randomness optimal
isolation lemma of \cite{CRS95} and yields a generalized isolation
lemma which works with respect to a set of linear forms over a base
set.