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 |