Let $\underline{x}\triangleq x_1,\dots,x_n$. Given a Boolean function $f:\{0,1\}^n\to\{0,1\}$, we say that $p(\underline{x})\in\Bbb{R}[\underline{x}]$ is an $\epsilon$-approximation to $f$ if for all $\underline{x}$, $|p(\underline{x})-f(\underline{x})|\leq\epsilon$. $\newcommand{\apxdeg}[0]{{{\mathsf{deg}}}}$ Let $\mathsf{deg}_\epsilon(f)$ be the minimum degree of multilinear real polynomial that $\epsilon$-approximates $f$.
Supposing that $\mathsf{deg}_{1/3}(f)\geq(\mathsf{deg}_0(f))^b$ with some $b\in(0.00001,1]$, are there constants $a_f\in(0,0.00001]$ such that, $\mathsf{deg}_\epsilon(f) \geq(\mathsf{deg}_0(f))^{a_f}$ at every $\epsilon\in(0,1)$?
Or is there an $f$ such that $\apxdeg_\epsilon(f) \leq \mathsf{polylog}(\apxdeg_0(f))$ at some $\epsilon\in(0,1)$?
Note that $a_f$ is unlikely to be independent of $f$. A closely related question corresponds to what is the highest error $\eta_f<1/2$ as it approaches $1/2$ beyond which no further decrease happens in degree except at exactly $\epsilon=\frac{1}2$.
Nisan-Szegedy result implies only a trivial lower bound of $$\lim_{\epsilon\rightarrow\frac{1}2^-}\mathsf{deg}_\epsilon(f)\geq 1.$$
For symmetric $f$ we can have $a_f$ close to $0.5$.
Is there a class of functions where a non-trivial lower-bound is not known?
Is there a class of functions it is conjectured approximate degree $\mathsf{deg}_{ \epsilon}(f)$ at some $\epsilon\in(0,\frac{1}2)$ can be polylogarithmically smaller than the exact degree given that $\mathsf{deg}_{1/3}(f)\geq(\mathsf{deg}_0(f))^b$ with some $b\in(0.00001,1]$?
When error approaches $1/2$. The bound is $\deg_{0}(f)\leq C_\epsilon(\deg_{\epsilon}(f))^8$ where $C_\epsilon$ depends on $\epsilon$. As $\epsilon$ approaches $0$, $C_\epsilon\rightarrow\infty$. So it is possible the upper bound is because $C_\epsilon\rightarrow\infty$ and $\deg_{\epsilon}(f)\rightarrow1$. This corresponds to $a_f=0$ in the question. Can this degenerate situation actually happen in a boolean function $f$?
