An (epsilon, delta)--Approximation Algorithm of the Number of Zeros for a Multilinear Polynomial over GF[q]
Title | An (epsilon, delta)--Approximation Algorithm of the Number of Zeros for a Multilinear Polynomial over GF[q] |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Karpinski, M., & Lhotzky B. |
Other Numbers | 652 |
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]. |
URL | http://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 |