An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]
Title | An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Grigoriev, D. Yu., & Karpinski M. |
Other Numbers | 657 |
Keywords | Approximation 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. |
URL | http://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 |