|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 1991 | Copyright 1991 University of Bonn, Department of Computer Science, Abt. V | |
|
897
|
An (\epsilon, \delta)-Approximation Algorithm of the Number of Zeros of a Multilinear Polynomial over GF[q]
Marek Karpinski, Barbara Lhotzky [Download PostScript] [Download PDF] We construct a polynomial time $(\e,\d)$-approximation algorithm for estimating the number of zeros of an arbitrary multilinear polynomial $f(\xes)$ over \gf{q}. This extends the recent result of Karpinski/Luby (\cite{KL90a}) on approximating the number of zeros of polynomials over the field \gf{2}. |
|
|
Last Change:
11/05/14 at 09:38:09
|
University of Bonn -> Department of Computer Science -> Chair V | |