Title: Deterministic identity testing for multivariate polynomials
Abstract: In this paper we present a simple deterministic algorithm for testing whether a multivariate polynomial f(x1, ..., xn) is identically zero, in time polynomial in m, n, log(d + 1) and H. Here m is the number of monomials in f, d is the maximum degree of a variable in f and 2H is the least upper bound on the magnitude of the largest coefficient in f. We assume that f has integer coefficients.The main feature of our algorithm is its conceptual simplicity. The proof uses Linnik's Theorem which is a deep fact about distribution of primes in an arithmetic progression.
Publication Year: 2003
Publication Date: 2003-01-12
Language: en
Type: article
Access and Citation
Cited By Count: 22
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot