# Different boolean degrees polynomially related-2?

Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).

Let $p$ be the minimum degree (of degree $d_f$) real polynomial that represents boolean function $f$ such that $f(x)=p(x)$.

Let $p_{0,\epsilon}$ be the minimum degree (of degree $d_{0,f,\epsilon}$) real polynomial that represents boolean function $f$ such that $$f(x)=0\implies p_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p_{1,\epsilon}$ be the minimum degree (of degree $d_{1,f,\epsilon}$) real polynomial that represents boolean function $f$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Is $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some $c_0$ and $c_1$?

Above holds if $\epsilon\in(0,1)$ Relations among different boolean approximations

There solution considered $0<\epsilon<\frac{1}{2}\leq\delta<1$. Solution showed relation between $d_{0,f,\epsilon},d_{0,f,\delta}$ is a linear function with constant multiplicative factor as long as we have fixed $\epsilon,\delta$.

This along with solution to another problem in Different boolean degrees polynomially related? shows $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some $c_0$ and $c_1$ holds if we have fixed $\epsilon,\delta$.

(1) I am most interested in case where we have not fixed $\delta$ and/or $\epsilon$. Say $\delta=1-\frac{1}{h(n)}$, $\epsilon=\frac{1}{g(n)}$ (that is either/both $\delta$ or/and $\epsilon$ changes) with some functions $g(n)$, $h(n)$ of $n$ (logarithmic/polynomial/exponential). I am interested in how fast do degrees (multiplicative factors) grow.

(2) There was a comment on sign degree. I understand sign degree is an useful parameter. However for sign degree as I understand ranges of functions involved are over $\Bbb R\backslash\{0\}$ (Only criteria is approximating function takes same sign as $f$). Here ranges are different.

1. The OR function has degree $n$, but it can be approximated by the function $(x_1+\cdots+x_n)/n$. This shows that $d_{1,\text{OR},1-1/n} = 1$.
2. If you have a polynomial $P$ representing $f$ in the sense that $P(x) = 0$ whenever $f(x) = 0$ and $|P(x)-1|<1$ whenever $f(x) = 1$, then for small enough $\epsilon > 0$, the function $P-\epsilon$ sign-represents $f$.
3. The correct tradeoff between (say) $d_{0,f,\epsilon}$ and $d_{0,f,\delta}$ for different $\epsilon,\delta$ can be studied using approximation theory, i.e. Chebyshev polynomials and the related Markov and Bernstein theorems and their ilk. The functions converting a $\delta$-approximation to an $\epsilon$-approximation can be constructed explicitly using Chebyshev polynomials, and lower bounds on their degrees can be obtained using Markov–Bernstein theorems. This is similar to the way that the tight bound $\Theta(\sqrt{n})$ for the approximate degree of the OR function $d_{\text{OR},\epsilon}$ is proved.
• $(x_1+\dots+x_n)/n)$ is $1$ if all $x_i$ are $1$. Else it is in $(\frac{1}{n},\frac{n-1}{n})$. I think this is $d_{1,AND,\frac{n-1}{n}}$. Am I correct in that degree of $d_{0,AND,\frac{n-1}{n}}$ seems to be $\Omega(n)$ since polynomial will have to pass through zero at almost every input $(1,1,\dots,1,1)$? Jan 6, 2015 at 19:56
• $d_{0,AND,\frac{n-1}{n}} = d_{1,NAND,\frac{n-1}{n}}=\Omega(n)$ also seems to be truth. Jan 6, 2015 at 20:00
• The approximate degree of AND is only $O(\sqrt n)$, and the appreciating function can be arranged to equal 1 exactly at the all ones input. This shows that $d_{1,AND,0.1}=O(\sqrt n)$, for example. Jan 6, 2015 at 22:16
• You're right that $d_{0,AND,1-1/n} = n$. In fact, $d_{0,AND,\epsilon} = n$ for all $\epsilon < 1$, since you can take the approximating function $f$ and normalize it by $f(1,\ldots,1)$ to get a function representing AND exactly, and we already know that this function has degree $n$. Jan 7, 2015 at 8:48