# #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT $$1$$: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials.

EDIT $$2$$: Theorem $$9$$ of this paper seems close to what we need. Maybe some close variant of Theorem $$9$$ is sufficient?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.