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 |