Department of Computer Science
 
Chair V

 
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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V