# $\#$P hardness of computing weighted sum of degree $2$ polynomials

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_i\in \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?

• The complexity of your problem highly depends on how $w_x$ are given in the input. If they are given explicitly as a list, your input being of size $O(2^n)$, you can obviously solve it in polynomial time.
– holf
Jul 7, 2021 at 9:25
• @holf I don't think $w$ is part of the input. So the question if whether there is a $w$ for which the problem is #P-hard. Jul 7, 2021 at 9:29
• ok thanks. This reminds me of #XOR-SAT (clauses are sums modulo $2$ of literals) being in $P$ while the weighted version (weights on literal) is #P-complete. I will look for the reference later and see if it is good enough for an answer.
– holf
Jul 7, 2021 at 12:34
• @holf Thanks! That will be very helpful. :) Jul 8, 2021 at 6:47
• I found this paper (www2.cs.sfu.ca/~abulatov/papers/weightedcsp.pdf) and I wonder if Theorem 9 of this paper can be applied to solve the problem. I could not work out the full details but it seemed close to what we need for this. Jul 10, 2021 at 18:20