Approximating the Number of Solutions of a GF[2] Polynomial
| Title | Approximating the Number of Solutions of a GF[2] Polynomial |
| Publication Type | Technical Report |
| Year of Publication | 1990 |
| Authors | Karpinski, M., & Luby M. |
| Other Numbers | 589 |
| Abstract | We develop a polynomial time Monte-Carlo algorithm for estimating the number of solutions to a multivariate polynomial over GF[2]. This gives the first efficient method for estimating the number of points on algebraic varieties ove GF[2], which has been recently proven to be #P-complete even for cubic polynomials. There are a variety of applications of our result, which will be discussed in the full version of the paper. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-025.pdf |
| Bibliographic Notes | ICSI Technical Report TR-90-025 |
| Abbreviated Authors | M. Karpinski and M. Luby |
| ICSI Publication Type | Technical Report |