<p>Consider polynomials <span class="math-container">$f: \{0, 1\}^{n} \rightarrow \{0, 1\}$</span> over <span class="math-container">$\mathbb{F}_2$</span> (addition and multiplication are taken modulo <span class="math-container">$2$</span>.) Consider integers <span class="math-container">$x \in \{0,1\}^{n}$</span>, written in binary. Let <span class="math-container">$\mathbb{Z}$</span> be the set of all integers.</p>
<p>Define
<span class="math-container">\begin{align}
\mathrm{gap}(f) &amp;= \sum_{x \in \{0, 1\}^{n}} (-1)^{f(x)} \\
&amp;= |\{x : f(x) = 0\}| - |\{x : f(x) = 1\}|.
\end{align}</span></p>
<p>According to <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.9881&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">this</a> paper, and <a href="https://people.maths.bris.ac.uk/%7Ecsxam/papers/lowdegree.pdf" rel="nofollow noreferrer">this</a> paper (Proposition <span class="math-container">$6$</span>), we know two things about <span class="math-container">$\mathrm{gap}(f)$</span>:</p>
<ol>
<li>It is (in the worst case) #P-hard to exactly compute <span class="math-container">$|\{x : f(x) = 0\}|$</span>, and hence, <span class="math-container">$\mathrm{gap}(f)$</span>, when <span class="math-container">$f$</span> is a polynomial of degree at most <span class="math-container">$3$</span>.</li>
<li><span class="math-container">$|\{x : f(x) = 0\}|$</span> and <span class="math-container">$\mathrm{gap}(f)$</span> can be computed in polynomial time when <span class="math-container">$f$</span> is a polynomial of degree at most <span class="math-container">$2$</span>.</li>
</ol>
<hr />
<p>Now, define a new quantity
<span class="math-container">\begin{align}
\mathrm{weightedgap}(f) &amp;= \sum_{x \in \{0, 1\}^{n}} w_{x} (-1)^{f(x)},~\text{where}
\end{align}</span>
<span class="math-container">\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}</span></p>
<p>Let <span class="math-container">$f$</span> be a degree <span class="math-container">$2$</span> polynomial.</p>
<p>I have two related questions:</p>
<ol>
<li>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?</li>
<li>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?</li>
</ol>
<p>Note that we have only one input here --- an efficient description of the degree <span class="math-container">$2$</span> function <span class="math-container">$f$</span>. The weight function is not a part of the input.</p>
<hr />
<p>I think both my computations are #P-hard. But I could not do a formal reduction.</p>
<p>Note that, unlike in the unweighted version, computing <span class="math-container">$|\{x : f(x) = 0\}|$</span> does not allow us to compute <span class="math-container">$\mathrm{weightedgap}(f)$</span>: we need to look at the actual values of the function in <span class="math-container">$\mathcal{O}(2^{n})$</span> places. So, I think it is very unlikely that we can do this in polynomial time.</p>
<p>EDIT <span class="math-container">$1$</span>: <a href="https://arxiv.org/pdf/1701.06386.pdf" rel="nofollow noreferrer">This</a> paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree <span class="math-container">$2$</span> polynomials.</p>
<p>EDIT <span class="math-container">$2$</span>: Theorem <span class="math-container">$9$</span> of <a href="https://www2.cs.sfu.ca/%7Eabulatov/papers/weightedcsp.pdf" rel="nofollow noreferrer">this</a> paper seems close to what we need. Maybe some close variant of Theorem <span class="math-container">$9$</span> is sufficient?</p>

CC BY-SA 4.0
2021-07-07T09:25:18.637Z
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
CC BY-SA 4.0
2021-07-07T09:29:48.470Z
@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.
domotorp
CC BY-SA 4.0
2021-07-07T12:34:27.327Z
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
CC BY-SA 4.0
2021-07-08T06:47:35.053Z
@holf Thanks! That will be very helpful. :)
AngryLion
CC BY-SA 4.0
2021-07-10T18:20:19.973Z
I found this paper (https://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.
AngryLion
CC BY-SA 4.0
2021-07-13T13:30:25.233Z
This is the paper I had in mind but have not checked yet. I should have more time next week but if you have time before to figure it out, I would be glad to read your answer ;).
holf
<cc.complexity-theory><counting-complexity><approximation-hardness><polynomials><finite-fields>
$\#$P hardness of computing weighted sum of degree $2$ polynomials
AngryLion
# $\#$P hardness of computing weighted sum of degree $2$ polynomials

(Asked by: username_0 on 2021-07-03)

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](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.9881&rep=rep1&type=pdf) paper, and [this](https://people.maths.bris.ac.uk/%7Ecsxam/papers/lowdegree.pdf) 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](https://arxiv.org/pdf/1701.06386.pdf) paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $2$ polynomials.

EDIT $2$: Theorem $9$ of [this](https://www2.cs.sfu.ca/%7Eabulatov/papers/weightedcsp.pdf) paper seems close to what we need. Maybe some close variant of Theorem $9$ is sufficient?

**Tags:** cc.complexity-theory, counting-complexity, approximation-hardness, polynomials, finite-fields
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  
> **username_1**: 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.  
> **username_0**: @holf Thanks! That will be very helpful. :)  
> **username_0**: I found this paper (https://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.  
> **username_1**: This is the paper I had in mind but have not checked yet. I should have more time next week but if you have time before to figure it out, I would be glad to read your answer ;).  

---

## 0 answers

