a point in $B(\vx, 2\eps)$, the behavior of the algorithm on $f_{\vx}$ and $g$ is identical, since the functions and all their derivatives agree outside this ball. Since an $\eps$-approximation must distinguish these two cases, for ${\mathcal{A}}$ to succeed, it must query this ball. The probability that ${\mathcal{A}}$ queries in this ball in any given step is at most $\frac{{\mathrm{vol}}(B(\vx, 2\eps))}{{\mathrm{vol}}(B(\mathbf{0}, 1))} = (2\eps)^d$. As ${\mathcal{A}}$ makes only $(1/4\eps)^d$ queries in total, the expected number of queries ${\mathcal{A}}$ makes to the ball $B(\vx, 2\eps)$ is at most $2^{-d}$. Thus with probability at least $1 - \frac{1}{2^d}$, the algorithm fails to distinguish $g$ from $f_\vx$, and hence cannot succeed.

Making the Separation Computational
-----------------------------------

The oracle-hardness of Theorem \[thm:no\_fast\_opt\] stems from possibly “hiding” a minimizer $\vx$ of $f$. The computational version of this hardness result will instead possibly hide an appropriate encoding of a satisfying assignment to a 3SAT formula.

There is a constant $\eps > 0$ such that it is NP-hard to $\eps$-optimize an efficiently computable Lipschitz function over the unit ball.

Let $\phi : \{0, 1\}^d \rightarrow {B_d(\mathbf{0}, 1)}$ be a map such that $\phi$ is efficiently computable, $\|\phi(\vy) - \phi(\vy')\| \geq 4\eps$ and such that given $\vx \in 