5
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – holf
    Jul 7, 2021 at 9:25
  • 3
    $\begingroup$ @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. $\endgroup$
    – domotorp
    Jul 7, 2021 at 9:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – holf
    Jul 7, 2021 at 12:34
  • $\begingroup$ @holf Thanks! That will be very helpful. :) $\endgroup$
    – AngryLion
    Jul 8, 2021 at 6:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – AngryLion
    Jul 10, 2021 at 18:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.