Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?

Question

Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient algorithm for calculating permanents of 0/1 matrices exactly. On the other hand, Valiant provided a polynomial time reduction from the permanent of an arbitrary matrix with integer entries to the permanent of a 0/1 matrix. Why could one not make use of this reduction, followed by an application of the JSV algorithm (which can efficiently approximate the permanents of matrices with nonnegative entries but cannot handle matrices with negative entries) to efficiently approximate the permanents of arbitrary integer matrices?

Answer 1

The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.

Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.

The type of reductions you'd need to reduce to JSV were named "approximation preserving reductions" by Dyer at al. An approximation-preserving reduction from a problem X to a problem Y is a way of turning an FPRAS for Y into an FPRAS for X (in a way that relativises). A simpler case of the same pattern is #DNF and #SAT:

• There is an approximation algorithm (an FPRAS) for counting solutions of a formula in disjunctive normal form.
• It is NP hard to approximate the number of solutions of a formula in conjunctive normal form to within a multiplicative constant (because it is NP hard to determine whether there is any satisfying assignment at all).
• There is a reduction from #SAT to #DNF: given a CNF formula $\phi$ on $n$ variables, replace all the conjunctions by disjunctions and vice versa. If the resulting formula has $x$ solutions, then $\phi$ has $2^n-x$ solutions.

There is no contradiction, because the reduction described above is not approximation-preserving. Another common non-approximation-preserving reduction for counting problems is polynomial interpolation.