<p>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.</p>
<p>If you're happy with finding the fraction of evaluation points over which the polynomial vanishes, up to an additive constant <span class="math-container">$\epsilon$</span>, then you can trivially evaluate at enough random points and take the empirical estimate.</p>

CC BY-SA 4.0
2020-08-13T04:15:51.137Z
2020-08-13T04:15:51.137Z
Mahdi Cheraghchi
<p>I have a polynomial <span class="math-container">$f(x_1,\ldots,x_{50})$</span> of 50 variables over binary field <span class="math-container">$GF(2)$</span>. I want
to evaluate at all <span class="math-container">$2^{50}$</span> 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?</p>

<ds.algorithms>
Polynomial evaluation at all different points
Sanu
# Polynomial evaluation at all different points

(Asked by: username_0 on 2020-08-12)

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?

**Tags:** ds.algorithms

---

## 1 answers

### Answer by username_1 on 2020-08-13. Score: 4

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.


---

