World's most popular travel blog for travel bloggers.

# Different boolean degrees polynomially related-2?

, ,
Problem Detail:

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.

###### Answered By : Yuval Filmus

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.