Minimum degree of a nonnegative polynomial uniformly approximating two constant values on two disjoint closed intervals This is a one-dimensional problem over $\mathbb{R}$. Given $y_0, y_1 \ge 0$ with $y_0 \neq y_1$, and closed intervals $I_0$ and $I_1$ with $I_0 \cap I_1 = \emptyset$, define a partial function $f(x) = y_i$ if $x \in I_i$ for $i \in \{0,1\}$. Given $\epsilon > 0$, what is the minimum degree (in terms of $\epsilon$) of a nonnegative polynomial that $\epsilon$-approximates $f$ uniformly? I.e., approximating polynomial should not differ by more than $\epsilon$ from $f$ where $f$ is defined, and on the rest of $\mathbb{R}$, it should just be nonnegative.
I am interested in both upper and lower bounds. In particular, is $O(\log(1/\epsilon))$ possible? If not, why not?
I apologize if I missed a classical theorem that gives the answer right away. My search online revealed Jackson-type theorems, but there are a few differences from the setting I am interested in - namely nonnegativity constraint and multiple compact sets, on which approximation should take place.
 A: First, let us ignore the nonnegativity constraint on the approximating polynomial.
By linear transformation of the variable, one may suppose that $I_{0}=[-A,-1]$ and 
$I_{1}=[1,B]$ and by a linear transformation on the approximating polynomial $P_{n}$, one may suppose that $y_{0}=-1$ and $y_{1}=1$ (since $y_{0}\neq y_{1}$). Now, by Chebyshev's theorem, a best polynomial approximant $P_{n}(x)$ to $\text{sgn}(x)$ on $I=I_{0}\cup I_{1}$ exists and is unique.
It has been proved in [1] that
$$C_{1}n^{-1/2}e^{-\eta n}\leq\|P_{n}-\text{sgn}\|_{I,\infty}=\inf_{p\in\mathcal{P}_{n}}\|p-\text{sgn}\|_{I,\infty}
\leq C_{2}n^{-1/2}e^{-\eta n},$$
where $C_{1}$ and $C_{2}$ are positive constants depending on $A$ and $B$, and $\eta$ is the critical value of the Green's function of the region $\mathbb{C}\setminus I$ with pole at infinity
(Ref. [1] seems difficult to find on the internet, but the above result is mentioned in Ref. [2] which is more accessible).
By the above inequality, one gets that, indeed, an $\epsilon$-approximation is achieved by a polynomial of degree $O(\log(1/\epsilon))$.
Concerning the nonnegativity constraint, obviously, it cannot be satisfied by odd approximating polynomials. 
For even degree $n$, it follows from the discussion on p.295 of [2] that the best approximant $P_{n}$ has at least $n-2$ critical points $x_{j}$, $j=1,\ldots,n-2$, which lie in $I$ and are alternating points for the error function, that is $|(P_{n}-\text{sign})(x_{j})|=\epsilon$. Hence, there is at most one critical point which is not an alternating point. This point is shown to belong to $\mathbb{R}\setminus[-A,B]$, and the corresponding critical value could, a priori, contradicts the nonnegativity constraint.
References
[1] W.H.J. Fuchs, On the degree of Chebyshev approximation on sets with several components, Izv. Akad. Nauk Armyan. SSR Ser. Mat. 13 (1978), 396-404, 541.
[2] A. Eremenko, P. Yuditskii, Polynomials of the best uniform approximation to sgn(x) on two intervals, J. Anal. Math. 114 (2011), 285-315. 
