Timeline for Computing a large permanent
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2013 at 9:44 | vote | accept | Felix Goldberg | ||
| Apr 30, 2013 at 16:15 | comment | added | Brendan McKay | (Ran out of characters) There is another method where you act like you are generating the whole search tree, but toss a coin at each node to decide whether or not to make its children. The bias of the coin, perhaps different at each level, is adjusted in advance so that what remains is not too large but still has a fair number of leaves. I've made some spot-on predictions using this method, but I've never seen it analyzed. I don't think it is equivalent to Knuth's method. | |
| Apr 30, 2013 at 16:09 | comment | added | Brendan McKay | Yes, I've seen that happen too, but I've also had some successes. One thing that I've found to help a lot is to collapse some number of lower levels in the tree into one level (so when you get to that level you perform an exhaustive search). That takes care of the situation where most paths die out just before the end. Another modification that should help here would be to define the tree to exclude all useless branches (using a flow algorithm for example) so that no paths die out at all. It will be much slower but also much less skewed I think. | |
| Apr 30, 2013 at 14:32 | comment | added | Timothy Chow | Brendan, the trouble with Knuth's method is that even though the mean of the estimator is correct, in many cases the distribution is highly skewed, so that with only polynomially many samples you will whp get a gross underestimate of the tree size. I can't be sure, but based on my past experience with similar problems, that's what I'd predict would happen for Felix's problem. This behavior of Knuth's algorithm is one reason why it's so remarkable that the MCMC methods give you guaranteed error bounds in polynomial time. | |
| Apr 30, 2013 at 11:09 | comment | added | Brendan McKay | A general estimation method that I think would work here starts by defining any backtrack program that counts the matchings in this bipartite graph. Then estimate the number of nodes at the right level of the search tree by using Knuth's method that involves tracing random paths. This gives an unbiased estimator, though it can be hard to get a reliable estimate of the precision. | |
| Apr 30, 2013 at 2:10 | comment | added | Timothy Chow | Scott, yes, I was assuming 0-1 matrices (or more generally nonnegative matrices) throughout; perhaps I should have been more explicit. The Jerrum-Sinclair-Vigoda result is also for nonnegative matrices only. | |
| Apr 29, 2013 at 21:32 | comment | added | Scott Aaronson | Timothy, when you write that there are algorithms that run in time polynomial in the value of the permanent, I assume you mean for nonnegative matrices only! For general matrices, I believe even deciding whether the permanent is (say) 0 or 1 is #P-hard under nondeterministic reductions. | |
| Apr 29, 2013 at 17:23 | history | answered | Timothy Chow | CC BY-SA 3.0 |