Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 1990 Copyright 1990 University of Bonn, Department of Computer Science, Abt. V
895

Approximating the Number of Solutions of a G F [ 2 ] Polynomial
Marek Karpinski, Michael Luby
[Download PostScript] [Download PDF]

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], 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.

Last Change: 11/05/14 at 09:36:40
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V