Approximating the Number of Solutions of a {\ G F [ 2 ]} Polynomial
Marek Karpiński, Michael G. Luby · 1990
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 over GF (2), the problem recently proven to be #P -complete even for the cubic polynomials. The number of applications of the result has been also discussed. Supported in part by the DFG Grant KA 673/4-1, and by the SERC Grant GR-E 68297. 1 Introduction The problem of counting the number of points on algebraic varieties is a fundamental issue in algebra, geometry, and especially in algebraic geometry (which can be `defined' as the study of polynomial equations over fields). It does have direct applications in the information and coding theory in computing weights of codes and channel-error probabilities, among other things (cf.[3, 7, 8]). Also ,several recent randomised designs of parallel algorithms over GF (q) raised the question on relative power of ran...