of the paper is organized as follows. We start with some preliminaries in Section \[sec:prelims\]. We give a simple separation between optimization and sampling in Section \[sec:simple\_sep\] and derive a computational version of this separation. Section \[sec:discrete\_to\_cont\] relates the discrete sampling/optimization problems on the hypercube to their continuous counterparts, and uses this connection to derive NP-hardness results for sampling for function families where optimization is easy. In Section \[sec:sharp\_threshold\], we prove the sharp threshold for $\lambda$. We describe additional related work in Section \[sec:related\]. Some missing proofs and strengthenings of our results are deferred to the Appendix.

Preliminaries {#sec:prelims}
=============

We consider real-valued functions $f : \Re^d \rightarrow  \Re$. We will be restricting ourselves to functions that are continuous and bounded. We say a function $f$ is $L$-Lipschitz if $f(\vx) - f(\vx') \leq L \cdot \|\vx - \vx'\|$ for all $\vx, \vx' \in \Re^d$. In this work, $\|\cdot\|$ will denote the Euclidean norm.

We will look at specific families of functions which have compact representations, and ask questions about efficiency of optimization and sampling. We will think of $d$ as a parameter, and look at function families such that at any function in the family can be computed in $poly(d)$ 