*Bounty: 100*

*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)$:

- 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$.
- $|{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:

- 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? - 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 one input here — an efficient description of the degree $2$ function $f$.

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.