Relative error estimation of a special type of GapP function

Question

Consider the functions included in the complexity class GapP.

We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly finding the sign of $f(x)$ (for a worst case function $f$) is #P-hard --- if we can find the sign, we can use a padding argument, coupled with binary search, to exactly find the value of the function. (For reference, see this.)

Now, consider another class of functions: let's name the class SpecialGap. A function $g(x)$ belongs to SpecialGap if and only if there exists a GapP function $f(x)$ such that $g(x) = f(x)^{2}$.

Note some properties of SpecialGap. In the worst case, computing the sign of a function in SpecialGap is easy --- it is always positive, as it is the square of a function. In the worst case, exactly computing a function from SpecialGap is #P-hard --- noting that #P functions are a subset of GapP functions, if we want to exactly estimate the value of a #P function, we use the procedure we have for finding the exact value of a SpecialGap function to find the exact value of the square of our desired #P function, and then we just take the square root to get the exact value of our #P function. Note that exactly estimating the value of a #P function is #P-hard.

Is multiplicatively estimating the value of a worst-case function, to inverse polynomial error, from SpecialGap also #P-hard?

---

Here's an attempt at a proof.

Consider a procedure to multiplicatively estimate (upto inverse polynomial relative error) the value of a SpecialGap function $g(x)$, where $g(x) = f(x)^{2}$, for a GapP function $f(x)$. Let the estimate be $\tilde g(x)$, where

\begin{equation} \left(1 - \frac{1}{p}\right)f(x)^{2} \leq \tilde g(x) \leq \left(1 + \frac{1}{p}\right)f(x)^{2}, \end{equation} for some polynomially bounded function $p$. Taking the square root, we have

\begin{equation} \left(1 - \frac{1}{2p}\right)|f(x)| \leq \sqrt{\tilde g(x)} \leq \left(1 + \frac{1}{2p}\right)|f(x)|, \end{equation} which is an inverse polynomial multiplicative error estimate to $|f(x)|$.

The proof now reduces to proving that for a function $f(x)$ belonging to GapP, in the worst case, it is #P-hard to have an inverse polynomial multiplicative error estimate to $|f(x)|$. I didn't have any idea on how to prove this. For one, since $|f(x)|$ is always positive, making use of a procedure to find the sign of $|f(x)|$, and then using binary search and padding, fails.

Answer 1

This is #P-hard, already for an arbitrary fixed constant approximation factor. As you noted, it allows you to approximate $|f(x)|$ for any GapP-function $f$, and therefore if $f$ is any #P (or GapP) function, it allows you to approximate $|f(x)-y|$ for a given $y$. With this, you can still compute $f(x)$ by a form of binary search.

Specifically, fix a constant $k\ge\gamma^2+1$, where $\gamma>1$ is the approximation factor. Starting with an initial estimate $0\le f(x)\le 2^{n^c}$, if you already have $a_0<a_1$ such that $a_0\le f(x)\le a_1$, you compute $a'_0\le a'_1$ such that $a'_0\le f(x)\le a'_1$ and $a'_1-a'_0\le\lfloor(1-\frac1k)(a'_1-a'_0)\rfloor$ by computing the approximations $d_0,d_1$ such that $$\gamma^{-1}d_i\le|f(x)-a_i|\le\gamma d_i,$$ and putting $$[a'_0,a'_1]=\begin{cases}\bigl[a_0,a_1-\lceil\frac1k(a_1-a_0)\rceil\bigr]&d_0\le d_1,\\{}\bigl[a_0+\lceil\frac1k(a_1-a_0)\rceil,a_1\bigr]&\text{otherwise.}\end{cases}$$ To see that this is correct: if, for example, $d_0\le d_1$, then $$f(x)-a_0\le\gamma^2(a_1-f(x)),$$ hence $$f(x)\le\frac{a_0+\gamma^2a_1}{\gamma^2+1}=a_1-\frac{a_1-a_0}{\gamma^2+1}\le a_1-\frac{a_1-a_0}k.$$ The case $d_1\ge d_0$ is symmetric.