suffices for this. Since $\mathcal{W}(P, Q)$ is bounded by the diameter times the statistical distance, this gives a $\eta + \exp(-\Omega(d))$ Wasserstein sampler for ${{\mathcal{D}}_f^{\lambda}}$. Similarly, a $\eta$ Wasserstein sampler for ${{\mathcal{D}}_f^{\lambda}}$ conditioned on the support of $\widehat{{{\mathcal{D}}_f^{\lambda}}}$ immediately yields an $O(\eta)$-sampler for ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$. Moreover, it is easy to check that this conditioning is on a constant probability event as long as $\eta < \frac 1 {16}$.

Optimization can be Easier than Sampling
----------------------------------------

Given the reduction from the previous section, there are many options for a starting discrete problem to apply the reduction. We will start from one of the most celebrated NP-hard problems. The NP-hardness of Hamiltonian Cycle dates back to @Karp72.

\[thm:hamcycle\_hardness\] Given a constant-degree graph $G = (V, E)$, it is NP-hard to distinguish the following two cases.

[Yes]{} Case:

:   $G$ has a Hamiltonian Cycle.

[No]{} Case:

:   $G$ has no Hamiltonian Cycle.

We can then amplify the gap between the number of long cycles in the two cases.

\[thm:count\_gap\_amplification\] Given a constant-degree graph $G = (V, E)$ and for $L= |V|/2$, it is NP-hard to distinguish the following two cases.

[Yes]{} Case:

:   $G$ has at least $1 + 2^{L}$ simple cycles of 