Publication Details
Title: Approximating the Number of Solutions of a GF[2] Polynomial
Author: M. Karpinski and M. Luby
Group: ICSI Technical Reports
Date: July 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-025.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-90-025
Bibliographic Reference:
M. Karpinski and M. Luby. Approximating the Number of Solutions of a GF[2] Polynomial. ICSI Technical Report TR-90-025, July 1990
Author: M. Karpinski and M. Luby
Group: ICSI Technical Reports
Date: July 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-025.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-90-025
Bibliographic Reference:
M. Karpinski and M. Luby. Approximating the Number of Solutions of a GF[2] Polynomial. ICSI Technical Report TR-90-025, July 1990