An (epsilon, delta)--Approximation Algorithm of the Number of Zeros for a Multilinear Polynomial over GF[q]

TitleAn (epsilon, delta)--Approximation Algorithm of the Number of Zeros for a Multilinear Polynomial over GF[q]
Publication TypeTechnical Report
Year of Publication1991
AuthorsKarpinski, M., & Lhotzky B.
Other Numbers652
Abstract

We construct a polynomial time (epsion, delta)-approximation for estimating the number of zeros of an arbitrary multi-linear polynomial f((x subscript 1), ..., (x subscript n)) over GF[q]. This extends the recent result of Karpinski/Luby [KL90] on approximating the number of zeros of polynomials over the field GF[2].

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-91-022.pdf
Bibliographic Notes

ICSI Technical Report TR-91-022

Abbreviated Authors

M. Karpinski and B. Lhotzky

ICSI Publication Type

Technical Report