\Exp_{\mu_s}\, [p(x)] = \Exp_{\mu_r}\, [p(x)]\end{aligned}$$ for any $s,r\in\{{\pm1,\pm2,\pm 3,\dots,\pm2^k}\}$ and any polynomial $p$ of degree no greater than $k.$ In the remainder of the proof, we will work with a fixed choice of weights $w_1,w_2,\dots,w_n$ for which the described distributions $\mu_s$ exist.

Suppose that $R^+(f,d)<\epsilon$ where $0<\epsilon<1$ and $0\leq d\leq k.$ Then there are degree-$d$ polynomials $p,q$ on $\Re^n\times \Re$ such that on the domain of $f,$ $$\begin{aligned}
0<(1-\epsilon)q(x,t)\leq p(x,t)f(x,t)\leq (1+\epsilon)q(x,t).
\label{eqn:multivariate-approximant}\end{aligned}$$ On the support of $\mu_s$ (for $s={\pm1,\pm2,\pm 3,\dots,\pm2^k}$), the linear form $$\begin{aligned}
\ell(x,s) = 2^{-k-1}{\left(\sum_{i=1}^nw_ix_i-s\right)}\end{aligned}$$ obeys $\ell(x,s)\in\{0,1,2,\dots,n\}$ and $f(x,\ell(x,s))=\sign s.$ Letting $t=\ell(x,s)$ in (\[eqn:multivariate-approximant\]) and passing to expectations, $$\begin{aligned}
0<\Exp_{x\sim\mu_s}
\left[q(x,\ell(x,s))\right]
(1-\epsilon)
\leq &\Exp_{x\sim\mu_s}
\left[p(x,\ell(x,s))\right]\sign s\\
\leq &\Exp_{x\sim\mu_s}
\left[q(x,\ell(x,s))\right]
(1+\epsilon).\end{aligned}$$ It follows from (\[eqn:mu\_s-equivalence-restated\]) that $
\Exp_{\mu_s} [p(x,\ell(x,s))] = P(s)$ and $\Exp_{\mu_s}[q(x,\ell(x,s))] = Q(s)$ for some $P,Q\in P_d$ and all $s.$ As a result, $R^+(\{{\pm1,\pm2,\pm 3,\dots,\pm2^k}\},d)\leq\epsilon,$ the approximant in question being $P/Q.$

It remains to rewrite the previous theorem in terms of functions on the hypercube $\zoo^{2n}$ rather than the set $\zoon\times\{0,1,2,\dots,n\}.$

\[thm:univariate-reduction\] Put $k=\lfloor\alpha n\rfloor,$ where $\alpha>0$ is the absolute constant from Theorem . Choose $w_1,w_2,\dots,w_n$ uniformly at random from $\{0,1,\dots,2^{k+1}-1\}.$ Define $f\colon\zoo^{2n}\to\moo$ by $$\begin{aligned}
f(x) = \sign \left( \frac12 + \sum_{i=1}^n w_ix_i -
2^{k+1}\sum_{i=n+1}^{2n} x_i\right).\end{aligned}$$ Then 