Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1991 Copyright 1991 Universität Bonn, Institut für Informatik, Abt. V 8565 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^{(q-1) \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