<p>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.</p>

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

<p>[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.</p>

CC BY-SA 4.0
2019-02-12T08:43:31.530Z
2019-02-12T08:43:31.530Z
smapers
<p>A famous result of <a href="https://www.cc.gatech.edu/~vigoda/Permanent.pdf" rel="nofollow noreferrer">Jerrum, Sinclair, and Vigoda</a> shows that there exists a polynomial-time algorithm which takes a bipartite graph <span class="math-container">$G$</span> and produces a random perfect matching <span class="math-container">$M$</span> of <span class="math-container">$G$</span> (assuming one exists), so that the distribution of <span class="math-container">$M$</span> 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 <span class="math-container">$G$</span>.</p>

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

<blockquote>
  <p>Is there any evidence that sampling a uniformly random perfect matching <span class="math-container">$M$</span> of a bipartite graph <span class="math-container">$G$</span> is computationally hard?</p>
</blockquote>

<p>The important bit that differentiates between this question and the JSV result is that the distribution of <span class="math-container">$M$</span> 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. </p>

<p>More generally, how does one show conditional hardness for sampling problems? </p>

CC BY-SA 4.0
2019-02-11T23:58:02.717Z
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: https://www.cc.gatech.edu/~vigoda/MCMC_Course/Sampling-Counting.pdf
Heng Guo
CC BY-SA 4.0
2019-02-12T04:08:33.300Z
@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.
Sasho Nikolov
<cc.complexity-theory><counting-complexity><permanent>
Computational hardness for sampling a uniform matching
Sasho Nikolov
# Computational hardness for sampling a uniform matching

(Asked by: username_0 on 2019-02-11)

A famous result of [Jerrum, Sinclair, and Vigoda](https://www.cc.gatech.edu/~vigoda/Permanent.pdf) 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?

**Tags:** cc.complexity-theory, counting-complexity, permanent
> **Comments:**
> **username_1**: 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: https://www.cc.gatech.edu/~vigoda/MCMC_Course/Sampling-Counting.pdf  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2019-02-12. Score: 2

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.


---

