
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 1991  Copyright 1991 Universität Bonn, Institut für Informatik, Abt. V  
898

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]
Dima Grigoriev, Marek Karpinski [Download PostScript] [Download PDF] We design the first polynomial time (for an arbitrary and fixed field $GF[q]$) $(\eps,\delta)$approximation algorithm for the number of zeros of arbitrary polynomial $f(x_1, \ldots, 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 (cf. \cite{BS90}). The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial $f(x_1, \ldots , x_n)$ over $GF[q]$ in the function on the number $m$ of its terms. The bounding ratio number is proved to be $m^{(q1) \log q}$ which is the main technical contribution of this paper and could be of independent algebraic interest. 

Last Change:
11/05/14 at 09:38:33
English 
Universität Bonn > Institut für Informatik > Abteilung V 