:   For $\lambda \geq 2d$ and $\eta < 1 - \exp(-\Omega(d))$, there is no efficient $\eta$-sampler for ${{\mathcal{D}}_f^{\lambda}}$ unless $NP=RP$.

In the statement above, efficiently computable means that given a $t$-bit representation of $\vx$, one can compute $f(\vx)$ to $t$ bits of accuracy in time $poly(d, t)$.

The easy optimization result above can be considerably strengthened. We can ensure that $\mathbf{0}$ is the optimizer of $f$ and that except with negligible probability, gradient descent starting at a random point will converge to this minimizer. Further, one can ensure that all local minima are global and that $f$ is strict-saddle. Thus not only is the function easy to optimize given the representation, black box oracle access to $f$ and its gradients suffices to optimize $f$. We defer details to the Appendix \[app:stronger\_optimizability\].

The hardness of sampling holds also for Wasserstein distance $\frac 1 {16}$, given Remark \[rem:sampling\_wasserstein\].

A Sharp Threshold for $\lambda$ {#sec:sharp_threshold}
===============================

We start with the following threshold result for sampling from the Gibb’s distribution on independent sets due to [@Weitz06; @SlyS12].

For any $\Delta \geq 6$, there is a threshold $\lambda_c(\Delta) > 0$ such that the following are true.

FPRAS for small $\lambda$:

:   For any $\lambda < 