Further, since we can find the planted cycle in $G$ efficiently, we can efficiently construct a minimizer $\vy^{(planted)}$ of $h$.

Suppose that $G$ has at least $(2^L+1)$ cycles of length $L$. In this case, the distribution ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$ restricted to the minimizers is uniform, and thus the probability mass on a specific minimizer $\vy^{(planted)}$ is at most $\frac 1 {2^{L}+1}$. This also therefore upper bounds the probability mass on $\vy^{(planted)}$ in the ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$.

On the other hand, suppose that planted cycle is the unique longest simple cycle in $G$. Thus the probability mass on $\vy^{(planted)}$ is at least $\exp(\lambda(d-L)) / Z_{h}^{\lambda, {\mathbb{H}_{d}}}$. Since every other cycle is of length at most $L-1$, and there are at most $2^d$ cycles, it follows that $\frac{Z_{h}^{\lambda, {\mathbb{H}_{d}}}}{\exp(\lambda(d-L))} \leq 1 + \frac{2^d}{\exp(\lambda)}$. For $\lambda \geq 2d$, this ratio is $(1+\exp(-d)) \leq (1 - \frac{1}{2^d})^{-1}$. The claim follows.

We can now apply Theorem \[thm:discrete\_to\_cont\_v1\] to derive the following result.

\[thm:opt\_easier\] There is a family ${\ensuremath{\mathcal{F}}}$ of functions $f : {B_d(0, R)}\rightarrow \Re$ such that the following hold.

Efficiency: 

:   Every $f \in {\ensuremath{\mathcal{F}}}$ is computable in time $poly(d)$.

Easy Optimization: 

:   An optimizer of $f$ can be found in time $poly(d)$

Sampling is NP-hard: 

