time and space.

We will look at constrained optimization in this work and our constraint set ${\mathcal{X}}$ will be a Euclidean ball. Our hardness results however do not stem from the constraint set, and nearly all of our results can be extended easily to the unconstrained case.

Given $\lambda >0$ and a function $f$, we let ${{\mathcal{D}}_f^{\lambda, {\mathcal{X}}}}$ denote the distribution on ${\mathcal{X}}$ with $\Pr[\vx] \propto \exp(-\lambda f(\vx))$. When ${\mathcal{X}}$ is obvious from context, we will usually omit it and write ${{\mathcal{D}}_f^{\lambda}}$. We will $Z_f^{\lambda, {\mathcal{X}}}$ for the [*partition function*]{} $\int_{{\mathcal{X}}} \exp(-\lambda f(\vx)) {\mathrm{d}}\vx$.

We will also look at real-valued functions $h : {\mathbb{H}_{d}} \rightarrow \Re$, where ${\mathbb{H}_{d}} = \{-1, 1\}^d$ is the $d$-dimensional hypercube. We will often think of a $\vy \in {\mathbb{H}_{d}}$ as being contained in $\Re^d$. Analagous to the Euclidean space case, we define ${\mathcal{D}}_{h}^{\lambda,{\mathbb{H}_{d}}}$ as the distribution over the hypercube with $\Pr[\vy] \propto \exp(-\lambda h(\vy))$, and define $Z_{h}^{\lambda,{\mathbb{H}_{d}}}$ to be $\sum_{\vy \in {\mathbb{H}_{d}}} \exp(-\lambda h(\vy))$.

We say that an algorithm $\eta$-samples from ${{\mathcal{D}}_f^{\lambda}}$ if it samples from a distribution that is $\eta$-close to ${{\mathcal{D}}_f^{\lambda}}$ in statistical distance. We will also use the [*Wasserstein*]{} distance between distributions on $\Re^d$, defined as $\mathcal{W}(P, Q) \stackrel{eq}= \inf_{\pi} \Ex_{(\vx, \vx') 