has the following corollary [@sherstov09hshs Thm. 1.7], in which we adopt the notation $\rdeg_\eps(f)= \min\{d :
R^+(f,d)\leq\epsilon\}.$

\[thm:approx-maj\] Let $\MAJ_n\colon \zoon\to\moo$ denote the majority function. Then $$\begin{aligned}
\rdeg_\epsilon(\MAJ_n)= 
{\begin{cases} 
\displaystyle 
\Theta{\left(
\log {\left\{\frac{2n}{\log(1/\epsilon)}\right\}}
\cdot 
\log \frac1\epsilon
\right)},
    &\qquad 2^{-n}<\epsilon<1/3,\\
\rule{0mm}{10mm}
\displaystyle 
\Theta{\left(1 + \frac{\log n}{\log\{1/(1-\epsilon)\}}\right)},
    &\qquad 1/3\leq \epsilon<1.
\end{cases}}\end{aligned}$$

Threshold degree. {#threshold-degree. .unnumbered}
-----------------

Let $f\colon X\to\moo$ be a given Boolean function, where $X\subset \Re^n$ is finite. The *threshold degree* of $f,$ denoted $\degthr(f),$ is the least degree of a polynomial $p(x)$ such that $f(x)\equiv\sign p(x).$ The term “threshold degree” appears to be due to Saks [@saks93slicing]. Equivalent terms in the literature include “strong degree” [@aspnes91voting], “voting polynomial degree” [@krause94depth2mod], “polynomial threshold function degree” [@odonnell03degree], and “sign degree” [@buhrman07pp-upp].

Given functions $f\colon X\to\moo$ and ${g}\colon
Y\to\moo,$ we let the symbol $f\wedge{g}$ stand for the function $X\times Y\to\moo$ given by $(f\wedge
{g})(x,y)=f(x)\wedge {g}(y).$ Note that in this notation, $f$ and $f\wedge f$ are completely different functions, the former having domain $X$ and the latter $X\times
X.$ An elegant observation, due to Beigel et al. [@beigel91rational], relates the notions of sign-representation and rational approximation for conjunctions of Boolean functions.

\[thm:rational-is-possible\] Let $f\colon X\to\moo$ and ${g}\colon Y\to\moo$ be given functions, where $X,Y\subseteq\Re^n.$ Let 