Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1990 Copyright 1990 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V