I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all points and check them. Can we do faster than this using some memory?
$\begingroup$
$\endgroup$
This problem is in general #P-complete, as you can for example encode a SAT instance as a polynomial over GF(2) and reduce #SAT to this problem. So all the standard hardness results apply to this.
If you're happy with finding the fraction of evaluation points over which the polynomial vanishes, up to an additive constant $\epsilon$, then you can trivially evaluate at enough random points and take the empirical estimate.
