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?

$\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 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 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 at 12:34
  • $\begingroup$ @holf Thanks! That will be very helpful. :) $\endgroup$
    – AngryLion
    Jul 8 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 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.