consider the case when ${\mathcal{X}}= B_d(\mathbf{0}, 1)$ is the unit norm Euclidean ball in $d$ dimensions. We let $\mathcal{F}_{Lip}$ be the family of all $1$-lipschitz functions from ${\mathcal{X}}$ to $\Re$. We show that for any $f \in \mathcal{F}_{Lip}$, exact sampling can be done in time $\exp(O(\lambda))$. On the other hand, for any algorithm, there is an $f \in\mathcal{F}_{Lip}$ that forces the algorithm to use $\Omega(\lambda/\eps)^d$ queries to $f$ to get an $\eps$-approximate optimal solution. Thus, e.g., for constant $\lambda$, sampling can be done in $poly(d)$ time, whereas optimization requires time exponential in the dimension. Moreover, for any $\lambda \leq d$, there is an exponential gap between the complexities of these two problems. Our lower bound proof is similar to the analagous claim in [@MaCJFJ18], but has better parameters due to the simpler setting. Our upper bound proof is signifantly simpler and gives an exact sampler.

There is an algorithm that for any $f \in \mathcal{F}_{Lip}$, outputs a sample from ${{\mathcal{D}}_f^{\lambda}}$ and makes an expected $O(\exp(2\lambda))$ oracle calls to computing $f$.

The algorithm is based on rejection sampling. We first compute $f(\mathbf{0})$ and let $M = f(\mathbf{0}) - 1$. By the Lipschitzness assumption, $f(\vx) \in  [M, M+2]$ for all $\vx$ in 