Talk:Computing the permanent

Some references[edit]

Hi. I have an as-yet unpublished paper about the hardness of computing permanent in the pipeline, so I prefer avoiding contributing to this article at this stage. I’ll watch the page, though. An informative survey that helped me a lot some time ago is Manindra Agrawal’s [1]. Especially, it contains a thorough overview of complexity results outside of Valiant’s #P-hardness, and it’s available on-line. From the algorithmic point of view, the most glaring omission seems to be that Wikipedia contains no page for Ryser’s formula, a fact noted at Wikipedia:Missing_science_topics/Maths24. Mathworld has a brief page: [2]. It might belong here or under Inclusion-exclusion principle, possibly both. Thore Husfeldt (talk) 15:34, 21 December 2008 (UTC)[reply]

By the way, consider using Computing the permanent as the “true” title of this article. I think it’s easiest to link to, and I believe one could establish that this phrase is the “most common” way of referring to this phenomenon in the scientific literature. A dirty Google scholar search finds 903 articles with that exact phrase. Thore Husfeldt (talk) 15:38, 21 December 2008 (UTC)[reply]

When I started this article which was derisively called "fork" by user:Nsk92 I considered this title (and did google search) as well, since it was in the title of Valiant's paper. However I felt unsure to use the gerund for the noun in the title (my bad English). Also I felt necessary to disambiguate "permanent" to "permanent of a matrix" so that my girlfriend would not be confused :-) Twri (talk) 22:47, 24 December 2008 (UTC)[reply]

Twri, considerations for your girlfriend notwithstanding, I read that as no objection. I’ll move the page; the current phrase as 10 google hits, including its own WP hits. The phrase Computing the permanent is the standard phrase in science texts for this phenomenon and has 70,000 google hits. It’s also easier to link to. Thore Husfeldt (talk) 07:51, 26 December 2008 (UTC)[reply]

A few papers on approximating permanents of 0-1 matrices:

I haven't taken the time to check to what extent they're made obsolete by the Jerrum/Sinclair/Vigoda paper already cited. We should probably at least cite the first of these, Jerrum and Sinclair, as a breakthrough work showing that some permanents could be approximated.

We should also have some mention here (as a method of computing permanents) and in the main permanent article of the fact that the permanent that counts the number of matchings of a bipartite planar graph can be calculated in polynomial time as a Pfaffian. —David Eppstein (talk) 04:20, 24 December 2008 (UTC)[reply]

“Glynn formula”[edit]

I’m not sure about the addition of a formula attributed to a recent paper of Glynn, called “Glynn formula” in the article. The result is from 2010, and so far has amassed 1 citation (a self-reference). I don’t think that’s sufficient impact to warrant prominent inclusion on this page. (On the other hand, the mechanisms for inclusion of this kind of material on Wikipedia—deciding weight and importance—are ill defined.) I’d like the input from other editors on this. Thore Husfeldt (talk) 12:49, 5 February 2011 (UTC)[reply]

Unless there's evidence that this has made an impact on the actual subject of the paper, algorithms for computing the permanent (not just formulas for the permanent), I'd say take it out. —David Eppstein (talk) 16:31, 5 February 2011 (UTC)[reply]

I would vote for keeping it. Although it has not been noticed much yet, I know from an expert on the subject that it is innovative and significant. McKay (talk) 14:32, 6 February 2011 (UTC)[reply]

I don’t like that argument at all. Even if we all agreed that it’s innovative and significant, we couldn’t just put it here on our own authority. But in particular, we can’t make that decision on somebody else’s. If there’s independent verifiable information about the importance of this result (such as on David Eppstein’s blog, or Brendan McKay’s website) I’m happy to consider it. But in general I’d like a secondary source (textbook, lecture notes, survey paper) or at least a bunch of citations before we advertise a result on Wikipedia. Thore Husfeldt (talk) 21:55, 6 February 2011 (UTC)[reply]

Some misrepresentation of the self reducibility reduction[edit]

Hi, This phrase is incorrect: Let $M(G)$ denote the number of perfect matchings in $G$ . Roughly, for any particular edge $e$ in $G$ , by sampling many matchings in $G$ and counting how many of them are matchings in $G\setminus e$ , one can obtain an estimate of the ratio $\rho ={\frac {M(G)}{M(G\setminus e)}}$ . The number $M(G)$ is then $\rho M(G\setminus e)$ , where $M(G\setminus e)$ can be approximated by applying the same method recursively.

This reduction works for matchings (https://www.cc.gatech.edu/~vigoda/MCMC_Course/Sampling-Counting.pdf) and for perfect matchings under assumptions that have a polynomial limit for the ratio of perfect matchings to near-perfect matchings (as is the case in Jerrum-Sinclair 1986), but doesn't work generally for perfect matchings as the ratio in one step can be exponentially large (an example appears in Broder's 1986 article).

I'm making a lecture about it for a seminar in MC methods and I eventually found out a full formal proof based on this entry can not be done. In Jerrum-Sinclair-Vigoda 2001 they used self-reducibility in a much more sophisticated way that depends on the weights in their MC construction so there's a constant lower bound for the ratios (and the ratios are not of perfect matchings counts for the subgraph).

Yotam.gafni (talk) 19:49, 14 April 2020 (UTC)[reply]

0-1 matrices[edit]

It would be beneficial to have a section on the special case of 0-1 matrices. Zaslav (talk) 18:53, 3 January 2024 (UTC)[reply]