the vertex, and we interpolate linearly in a small ball. See Figure \[fig:functions\_h\_f\] for an illustration.

Formally, let ${\texttt{round}}: \Re \rightarrow \{-1, 1\}$ be the function that takes the value $1$ for $x \geq 0$ and $-1$ otherwise, and let ${\texttt{round}}: \Re^d \rightarrow {\mathbb{H}_{d}}$ be its natural vectorized form that applies the function coordinate-wise. Let $g(\vx) = \|\vx - {\texttt{round}}(\vx)\|$ denote the Euclidean distance from $\vx$ to ${\texttt{round}}(\vx)$. Let ${s}= 2M$. The function $f$ is defined as follows: $$\begin{aligned}
    f(\vx) &= \left\{\begin{array}{ll}
                                                  h({\texttt{round}}(\vx)) + {s}\cdot g(\vx) & \mbox{ if }  g(\vx) \leq \frac{M - h({\texttt{round}}(\vx))}{{s}}\\
                          M & \mbox{ if } g(\vx) \geq \frac{M - h({\texttt{round}}(\vx))}{{s}}\\
                     \end{array}
              \right.
  \end{aligned}$$ It is easy to verify that $f$ is continuous. Moreover, since $M \geq 2d$, and $h$ has range $[0,d]$, the value $\frac{M - h({\texttt{round}}(\vx))}{{s}}$ is in the range $[\frac 1 4, \frac 1 2]$. It follows that $f$ takes the value $M$ outside balls of radius $\frac 1 2$ around the hypercube vertices, and is strictly smaller than $M$ in balls for radius $\frac 1 4$.

Since ${\texttt{round}}(\vx)$ is easy to compute, this implies that $f$ can be computed in polynomial time, using a single oracle call to $h$. Moreover it is 