An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]

TitleAn Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]
Publication TypeTechnical Report
Year of Publication1991
AuthorsGrigoriev, D. Yu., & Karpinski M.
Other Numbers657
KeywordsApproximation Algorithms, Counting Problems, Finite Fields, Multivariate Polynomials
Abstract

We design the first polynomial time (for an arbitrary and fixed field GF[q]) (epsilon,delta)-approximation algorithm for the number of zeros of arbitrary polynomial f(x_1, ... ,x_n) over GF[q].It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF[2] (like GF[3]), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x_1, ... ,x_n) over GF[q] in the function on the number m of its terms. The bounding ratio number is proved to be m**((q-1) log q) which is the main technical contribution of this paper and could be of independent algebraic interest.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1991/tr-91-027.pdf
Bibliographic Notes

ICSI Technical Report TR-91-027

Abbreviated Authors

D. Grigoriev and M. Karpinski

ICSI Publication Type

Technical Report