{B_d(\phi(\vy), 2\eps)}$, we can efficiently recover $\vy$. For a small enough absolute constant $\eps$, such maps can be easily constructed using error correcting codes and we defer details to Appendix \[app:eccs\].

We start with an an instance $I$ of 3SAT on $d$ variables, and define $f$ as follows. Given a point $\vx$, we first find a $\vy \in \{0, 1\}^d$, if any, such that $\vx \in {B_d(\phi(\vy), 2\eps)}$. If no such $\vy$ exists, $f(\vx)$ is set to $0$. If such a $\vy$ exists, we interpret it as an assignment to the variables in the 3SAT instance $I$ and set $f(\vx)$ to be $\min(0, \|\phi(\vy) - \vx\| - 2\eps)$ if $\vy$ is a satisfying assignment to instance $I$, and to $0$ otherwise.

It is clear from definition that $f$ as defined is efficiently computable. Moreover, the minimum attained value for $f$ is $-2\eps$ if $I$ is satsifiable, and $0$ otherwise. Since distinguishing between these two cases is NP-hard, so is $\eps$-optimization of $f$.

We note that assuming the exponential time hypothesis, this implies the $\exp(\Omega(d))$ oracle complexity lower bound of Theorem \[thm:no\_fast\_opt\].

Relating Discrete and Continuous Settings {#sec:discrete_to_cont}
=========================================

For any function $h$ on the hypercube, we can construct a function 