find a particular minimizer $\vy^{(planted)}$ of $h$ on ${\mathbb{H}_{d}}$.

Sampling is hard:

:   Let $\lambda \geq 2d$. It is NP-hard to distinguish the following two cases, for $L = \Omega(d)$:

    [Yes]{} Case:

    :   $\Pr_{\vy \sim {\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}}[\vy = \vy^{(planted)}] \leq \frac 1 {2^L}$

    [No]{} Case:

    :   $\Pr_{\vy \sim {\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}}[\vy = \vy^{(planted)}] \geq 1 - \frac 1 {2^L}$

    In particular this implies that $1-\frac{1}{2^{L-2}}$-sampling from ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$ is NP-hard.

Let $G = (V, E)$ a graph produced by Theorem \[thm:count\_gap\_amplification\] and let $d = |E|$. A vertex $\vy$ of the hypercube ${\mathbb{H}_{d}}$ is easily identified with a set $E_{\vy} \subset E$ consisting of the edges $\{e \in E : y_{e'} = 1\}$. The function $h_1(\vy)$ is equal to zero if $E_\vy$ does not define a simple cycle and is equal to the length of the cycle otherwise. To convert this into a minimization problem, we define $h(\vy) = d - h_1(\vy)$. It is immediate that a minimizer of $h$ corresponds to a longest simple cycle in $G$.

Given a vertex $\vy$, testing whether $E_{\vy}$ is a simple cycle can done efficiently, and the length of the cycle is simply $|E_{\vy}|$. This implies that $h$ can be efficiently computed on ${\mathbb{H}_{d}}$. 