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).

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 5, 2015 at 1:11
  • $\begingroup$ @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$. $\endgroup$ Jan 5, 2015 at 9:06
  • $\begingroup$ @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})$? $\endgroup$
    – Turbo
    Jan 5, 2015 at 9:32
  • $\begingroup$ @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. $\endgroup$ Jan 5, 2015 at 12:22
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Jan 5, 2015 at 23:15

1 Answer 1


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})$.

  • $\begingroup$ 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$. $\endgroup$
    – Turbo
    Jan 5, 2015 at 10:37
  • $\begingroup$ 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. $\endgroup$ Jan 5, 2015 at 11:40
  • $\begingroup$ 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$. $\endgroup$ Jan 5, 2015 at 12:21
  • $\begingroup$ 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$). $\endgroup$
    – Turbo
    Jan 6, 2015 at 1:46
  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Jan 6, 2015 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.