<p>I'm trying to understand the statement in the introduction (pg 1) of this <a href="https://arxiv.org/pdf/1704.03486.pdf" rel="nofollow noreferrer">work</a> by Anari et all on approximating the permanent <span class="math-container">$\text{per}(A)$</span> of a positive semi-definite matrix <span class="math-container">$A$</span>.</p>
<p>The statement, I'm wondering about is where the authors write &quot;it is <span class="math-container">$\#P$</span> hard to compute the sign of <span class="math-container">$\text{per}(A)$</span>, essentially ruling out a multiplicative approximation&quot;</p>
<p>I was hoping to understand this statement more clearly. Intuitively, one cannot approximate something without knowing the sign of it, but I was hoping for a more precise understanding than that. I understand that a multiplicative approximation within a factor <span class="math-container">$\epsilon$</span> involves outputting a <span class="math-container">$Z$</span> such that
<span class="math-container">$$\big| \frac{\text{per}(A)-Z}{Z} \big| \leq \epsilon$$</span></p>
<p>Is there a way to say this formally?</p>

CC BY-SA 4.0
2023-09-03T12:16:13.213Z
For $\epsilon < 1$, the statement is straightforward. The approximation must have the same sign as the value of the permanent, thus any multiplicative approximation would determine the sign of the permanent. Going by the definition and the use of $\epsilon$ which typically denotes an arbitrarily small quantity, I assume that values $\epsilon > 1$ are not of interest.
chazisop
CC BY-SA 4.0
2023-09-03T13:56:28.487Z
@chazisop. That's what I was thinking. But I think the paper proves a result for approximations of the permanent with $\epsilon >> 1$.
user135520
CC BY-SA 4.0
2023-09-03T14:31:54.933Z
The displayed definition only makes sense for $\epsilon<1$. Multiplicative approximation within a factor $c\gg1$ should be defined so that $c^{-1}\le\mathrm{per}(A)/Z\le c$ or something like that. In any case, preservation of sign should follow from the definition by a trivial algebraic manipulation. If it doesn’t, you are using a wrong definition. I don’t think it’s very productive to spend so much time on this point; just consider preservation of sign as a part of the definition and move on.
Emil Jeřábek
CC BY-SA 4.0
2023-09-03T14:36:36.037Z
@EmilJeřábek The paper actually shows provides a $c >>1$, such that $c^{-1} \leq per(A)/Z \leq 0$ which is basically what you wrote.  So I must be using the wrong definition of multiplicative approximation, which changes the question a bit.
user135520
CC BY-SA 4.0
2023-09-03T15:12:24.107Z
I suppose the right definition that works for both small and large $\epsilon>0$ and possibly negative functions is that $g$ is a multiplicative approximation of $f$ within $\epsilon$ if $(1+\epsilon)^{-1}\le g(x)/f(x)\le1+\epsilon$. This still doesn't work if $f(x)$ may be $0$ (in which case the definition should make $g(x)=0$ as well).
Emil Jeřábek
CC BY-SA 4.0
2023-09-04T15:15:58.897Z
@user135520 I am not an expert of the field, but whenever I encountered such types of approximation, they were referred to as factor approximation, typically with the factor included, e.g., $c$-factor approximation for $c>1$ such that either $cZ$ upper bounds the value for upper bounds or $c^{-1}Z$ lower bounds the value. In particular factor approximation typically is a one-sided bound, thus a weaker notion than multiplicative approximation.
chazisop
<cc.complexity-theory><approximation-hardness><permanent>
If it is $\#{P}$-hard to compute the sign of the permanent of any matrix, does that imply difficulty in relative approximation of the permanent?
user135520
# If it is $\#{P}$-hard to compute the sign of the permanent of any matrix, does that imply difficulty in relative approximation of the permanent?

(Asked by: username_0 on 2023-09-02)

I'm trying to understand the statement in the introduction (pg 1) of this [work](https://arxiv.org/pdf/1704.03486.pdf) by Anari et all on approximating the permanent $\text{per}(A)$ of a positive semi-definite matrix $A$.

The statement, I'm wondering about is where the authors write "it is $\#P$ hard to compute the sign of $\text{per}(A)$, essentially ruling out a multiplicative approximation"

I was hoping to understand this statement more clearly. Intuitively, one cannot approximate something without knowing the sign of it, but I was hoping for a more precise understanding than that. I understand that a multiplicative approximation within a factor $\epsilon$ involves outputting a $Z$ such that
$$\big| \frac{\text{per}(A)-Z}{Z} \big| \leq \epsilon$$

Is there a way to say this formally?

**Tags:** cc.complexity-theory, approximation-hardness, permanent

> **Comments:**
> **username_1**: For $\epsilon < 1$, the statement is straightforward. The approximation must have the same sign as the value of the permanent, thus any multiplicative approximation would determine the sign of the permanent. Going by the definition and the use of $\epsilon$ which typically denotes an arbitrarily small quantity, I assume that values $\epsilon > 1$ are not of interest.  
> **username_0**: @username_1. That's what I was thinking. But I think the paper proves a result for approximations of the permanent with $\epsilon >> 1$.  
> **username_2**: The displayed definition only makes sense for $\epsilon<1$. Multiplicative approximation within a factor $c\gg1$ should be defined so that $c^{-1}\le\mathrm{per}(A)/Z\le c$ or something like that. In any case, preservation of sign should follow from the definition by a trivial algebraic manipulation. If it doesn’t, you are using a wrong definition. I don’t think it’s very productive to spend so much time on this point; just consider preservation of sign as a part of the definition and move on.  
> **username_0**: @EmilJeřábek The paper actually shows provides a $c >>1$, such that $c^{-1} \leq per(A)/Z \leq 0$ which is basically what you wrote.  So I must be using the wrong definition of multiplicative approximation, which changes the question a bit.  
> **username_2**: I suppose the right definition that works for both small and large $\epsilon>0$ and possibly negative functions is that $g$ is a multiplicative approximation of $f$ within $\epsilon$ if $(1+\epsilon)^{-1}\le g(x)/f(x)\le1+\epsilon$. This still doesn't work if $f(x)$ may be $0$ (in which case the definition should make $g(x)=0$ as well).  
> **username_1**: @username_0 I am not an expert of the field, but whenever I encountered such types of approximation, they were referred to as factor approximation, typically with the factor included, e.g., $c$-factor approximation for $c>1$ such that either $cZ$ upper bounds the value for upper bounds or $c^{-1}Z$ lower bounds the value. In particular factor approximation typically is a one-sided bound, thus a weaker notion than multiplicative approximation.  

---

## 0 answers

