#StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields $#$P hardness of computin…

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

  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_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:

  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 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.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $2$ polynomials


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.