Timeline for Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 29, 2013 at 1:25 | vote | accept | Adrian | ||
| Nov 28, 2013 at 11:15 | comment | added | Colin McQuillan | @Adrian: in the reduction given in Proposition 3.4 in "The complexity of computing the permanent", the primes "$p_i$" are generally less than the absolute value of the permanent, for which only the upper bound "$\mu^n n!$" is known. | |
| Nov 28, 2013 at 1:52 | comment | added | Adrian | I see. The problem of calculating the permanent exactly is just as hard if the matrix has arbitrary integer entries as if the matrix is 0/1. However, allowing for approximation separates the problem into an easy case (nonnegative entries) and a hard case (arbitrary integer entries). I suppose I'm still confused on the point that the reduction is not approximation-preserving. By construction, the absolute value of the permanent cannot be greater than what you mod out by, so there are only two possible cases. What if I were to instead ask for only the absolute value of the permanent? | |
| Nov 27, 2013 at 11:23 | history | answered | Colin McQuillan | CC BY-SA 3.0 |