# Relations among different boolean approximations

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,\frac{1}{2})$ as mentioned here in link Different boolean degrees polynomially related?.

However what happens if $\epsilon\in(0,1)$ instead of $(0,\frac{1}{2})$ (does polynomial relation still hold)?

That is we consider $0<\epsilon<\frac{1}{2}\leq\delta<1$.

Note that defining $p_\delta$ makes little sense if $\delta\in[\frac{1}{2},1)$.

I am most interested in $\delta=1-\frac{1}{h(n)}$ with some function of $n$ (logarithmic/polynomial/exponential).

• I can't understand the question. I get stuck at your second sentence. I can't understand the sentence "Let p be the minimum degree real polynomial that represents f with degree $d_f$." What if the minimum degree polynomial that represents $f$ doesn't have degree $d_f$? And, what's $f$? Please make your question self-contained, and please make sure to proof-read it and state the question precisely. If the question is not well-posed, you're not likely to get a useful answer. – D.W. Jan 5 '15 at 1:11
• @D.W. You can think of $p$ as the Fourier expansion or $f$, as the unique multilinear polynomial equal to $f$, or as the real polynomial of minimal degree that equals $f$. – Yuval Filmus Jan 5 '15 at 9:06
• @YuvalFilmus Fourier/polynomial interpretation comes from fact that $\chi_S=\prod_{i\in S}(-1)^{x_i}=\prod_{i\in S}(1-2{x_i})$? – Turbo Jan 5 '15 at 9:32
• @Turbo Yes, that's the idea. It is even more convenient to just assume that the inputs are $\pm 1$ rather than $0/1$, and then the Fourier expansion is the same as the unique multilinear extension. – Yuval Filmus Jan 5 '15 at 12:22
• @YuvalFilmus, that still doesn't help. Is that sentence meant as a definition of $p$? But what if there is no polynomial $p$ that satisfies all the requirements? Alternatively, is that sentence meant as a definition of $d_f$? If so, it should be re-written, because that wasn't clear (to me). I shouldn't have to guess at the meaning. – D.W. Jan 5 '15 at 23:15

The new parameters are polynomially related to the old parameters. In fact, for every $0<\delta,\epsilon<1$ it is the case that $d_{0,f,\epsilon} = \Theta_{\delta,\epsilon}(d_{0,f,\delta})$. This is proved in the same way that the usual relation regarding $d_{f,\epsilon}$ is proved, as detailed below.
Suppose we are given $0<\delta,\epsilon<1$. Let $g$ be some continuous function satisfying $g(0) = 0$ and $g(x) = 1$ for $1-\delta \leq x \leq 1+\delta$. The Weierstrass approximation theorem shows that there is some polynomial $G$ such that $|G(0)| \leq \epsilon/2$ and $|G(x)-1| \leq \epsilon/2$ for all $1-\delta \leq x \leq 1+\delta$. Let $G_0(x) = G(x) - G(0)$, so that $G_0(0) = 0$ and $|G_0(x)-1| \leq \epsilon$ for all $1-\delta \leq x \leq 1+\delta$. The polynomial $P = G_0(p_{0,\delta})$ has degree $(\deg G_0)d_{0,f,\delta}$ and satisfies $P(x) = 0$ whenever $f(x) = 0$, and $|P(x)-1| \leq \epsilon$ whenever $f(x) = 1$. This shows that $d_{0,f,\epsilon} \leq (\deg G_0) d_{0,f,\delta}$. Since $G_0$ only depends on $\delta,\epsilon$, this proves that $d_{0,f,\epsilon} = O_{\delta,\epsilon}(d_{0,f,\delta})$.
• From answer it looks like $deg(G_0)$ could be very large. So in fact we may not have a polynomial relation. That is there is no unique bound on polynomial exponent. $deg(G_0)\rightarrow\infty$ as $\epsilon\rightarrow 1$ for any fixed $\delta$. – Turbo Jan 5 '15 at 10:37
• You can probably make $\deg G_0$ polynomial in $1/\delta$. But it makes no difference – for each fixed $\delta,\epsilon$, the two degrees differ by a multiplicative constant. If you're interested in the limit $\epsilon\to1$, this is yet another notion of complexity. – Yuval Filmus Jan 5 '15 at 11:40
• Taking the limit $\epsilon\to1$, we get something very similar to sign degree. There could be a big gap between this and other complexity measures. For example, if $f$ is the NAND function on $n$ variables then $d_{f,\epsilon} = \Theta(\sqrt{n})$ but the linear polynomial $P = 1-(x_1+\cdots+x_n)/n$ satisfies $P(x) = 0$ when $f(x) = 0$, and otherwise $0 < P(x) \leq 1$. – Yuval Filmus Jan 5 '15 at 12:21
• 1) what is sign degree? How does it come in the picture (I notice strong/weak degree in Jukna's book under sign approximation) 2) Let me make $\epsilon$ and $\delta$ more precise. We have $0<\epsilon<\frac{1}{2}\leq\delta<0$ where $\delta=1-\frac{1}{h(n)}$ for some function $h(n)$ (logarithmic or polynomial or exponential). In this case how fast does $deg(G_0)$ grow in relation $d_{0,f,\epsilon}=deg(G_0)d_{0,f,\delta}$ (Note $d_{0,f,\delta}<d_{0,f,\epsilon}$ since $\epsilon<\delta$). – Turbo Jan 6 '15 at 1:46
• I cannot imagine of any natural function $g$ which is continuous satisfying $g(0)=0$ and $g(x)=1$ for $1−δ≤x≤1+δ$ Does there exist such a function? – Turbo Jan 6 '15 at 1:52