Publication Details
Title: An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]
Author: D. Grigoriev and M. Karpinski
Group: ICSI Technical Reports
Date: April 1991
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-027.pdf
Overview:
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.
Author: D. Grigoriev and M. Karpinski
Group: ICSI Technical Reports
Date: April 1991
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-027.pdf
Overview:
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.
Keywords: Approximation Algorithms, Counting Problems, Multivariate Polynomials, Finite Fields.
Bibliographic Information:
ICSI Technical Report TR-91-027
Bibliographic Reference:
D. Grigoriev and M. Karpinski. An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]. ICSI Technical Report TR-91-027, April 1991