A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one exists), so that the distribution of $M$ is arbitrarily close to uniform in total variation distance. This is sufficient to give a randomized approximation scheme for the number of perfect matchings of $G$.

Since Valiant has shown that the permanent of a binary matrix is $\#\mathsf{P}$-hard, we do not expect to be able to compute the number of perfect matchings of a bipartite graph $G$ exactly. I suspect that generating a uniformly random perfect matching of $G$ is also hard, but I do not know of any complexity theory evidence for this. So my question is:

Is there any evidence that sampling a uniformly random perfect matching $M$ of a bipartite graph $G$ is computationally hard?

The important bit that differentiates between this question and the JSV result is that the distribution of $M$ is required to be exactly uniform. Any computational hardness here would have to be conditional, because if we could compute the number of perfect matchings in any bipartite graph, then we could also sample a uniformly random matching.

More generally, how does one show conditional hardness for sampling problems?

  • $\begingroup$ Given the approximate counter, we can have an exact sample with polynomial running time in expectation. See e.g. Lemma 4 of Vigoda's notes: cc.gatech.edu/~vigoda/MCMC_Course/Sampling-Counting.pdf $\endgroup$
    – Heng Guo
    Feb 11, 2019 at 23:58
  • $\begingroup$ @HengGuo Oh, silly of me to forget that, I have seen this before. So this problem is not hard, at least not for expected poly time algorithms. I guess one can look for hardness for exact sampling with algorithms that take polytime in the worst case, but then you'd need a notion of hardness that separates expected poly time and poly time. Anyways, feel free to post an answer and I'll accept it. $\endgroup$ Feb 12, 2019 at 4:08

1 Answer 1


Concerning your general question, I think the paper by Aaronson and Arkhipov [1] on boson sampling is a good example. They show that if there exists a classical poly-time algorithm that exactly (or at least "extremely accurate" as they state it) samples from a certain distribution, then the polynomial hierarchy collapses up to some level.

To prove the same thing for an approximate sampling algorithm, they must rely on some unproven conjectures.

[1] Aaronson, Scott, and Alex Arkhipov. "The computational complexity of linear optics." Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, 2011.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.