Title: Randomness efficient identity testing of multivariate polynomials
Abstract: 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.
Publication Year: 2001
Publication Date: 2001-07-06
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 157
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot