Randomness efficient identity testing of multivariate polynomials

We present a randomized polynomial time algorithm to determine if a multivariate polynomial is zero using O(\log mnδ) random bits where n is the number of variables, m is the number of monomials, and δ is the total degree of the unknown polynomial. All other known randomized identity tests (see for example [7, 12, 1]) use ω(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 [8] and yields a generalized isolation lemma which works with respect to a set of linear forms over a base set.

Authors

• Adam R. Klivans
• Daniel A. Spielman

Keywords

No keywords are indexed for this paper.