I'm trying to understand the statement in the introduction (pg 1) of this work 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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – chazisop
    Commented Sep 3, 2023 at 12:16
  • $\begingroup$ @chazisop. That's what I was thinking. But I think the paper proves a result for approximations of the permanent with $\epsilon >> 1$. $\endgroup$
    – user135520
    Commented Sep 3, 2023 at 13:56
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 3, 2023 at 14:31
  • 1
    $\begingroup$ 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). $\endgroup$ Commented Sep 3, 2023 at 15:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – chazisop
    Commented Sep 4, 2023 at 15:15


Your Answer

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