<p>If I understand correctly you are asking about the relationship between the degree necessary for exact representation and the degree necessary for approximate representation.  <a href="http://www.cs.huji.ac.il/~noam/degree.ps" rel="nofollow">The seminal paper by Nisan and Szegedy</a> shows that for $\epsilon$ constant these degrees are polynomially related.</p>

CC BY-SA 3.0
2015-06-05T19:05:52.117Z
sorry I am not asking this. In Nisan-Szegedy, $\lim_{\epsilon\rightarrow\frac{1}2^-}deg_{\epsilon}(f)\geq1$ is best lower bound on degree for a general $f$. My question is could this lower bound depend on $0$-error polynomial degree.
Turbo
CC BY-SA 3.0
2015-06-08T10:59:00.470Z
Could you remove your answer? It is receiving upvotes and people who may be interested might think this question has a reasonable answer already.
Turbo
CC BY-SA 3.0
2015-06-05T14:12:38.207Z
2015-06-05T14:12:38.207Z
Manu
<p>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$.</p>

<blockquote>
  <p>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)$?</p>
  
  <p>Or is there an $f$ such that 
  $\apxdeg_\epsilon(f) \leq \mathsf{polylog}(\apxdeg_0(f))$ at some $\epsilon\in(0,1)$?</p>
  
  <p>Note that $a_f$ is unlikely to be independent of $f$. A closely related question corresponds to what is the highest error $\eta_f&lt;1/2$ as it approaches $1/2$ beyond which no further decrease happens in degree except at exactly $\epsilon=\frac{1}2$.</p>
  
  <p><a href="http://www.cs.huji.ac.il/~noam/degree.ps" rel="nofollow">Nisan-Szegedy result</a> implies only a trivial lower bound of
  $$\lim_{\epsilon\rightarrow\frac{1}2^-}\mathsf{deg}_\epsilon(f)\geq 1.$$</p>
</blockquote>

<p>For symmetric $f$ we can have $a_f$ close to $0.5$.</p>

<p>Is there a class of functions where a non-trivial lower-bound is not known?</p>

<p>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]$?</p>

<hr>

<hr>

<p>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$?</p>

CC BY-SA 3.0
2015-06-05T19:51:45.787Z
@Trurbo, I think we have told you a couple of times by now that you should spend more time thinking and formulating your questions _before_ posting them here. It is becoming really annoying that you post a question, people answer what you have posted, and then you say it is not what you are looking for and change question you have asked. I think the frequency of this shows that you don't do your homework before posting your questions.
Kaveh
CC BY-SA 3.0
2015-06-06T05:04:07.620Z
@kaveh please check what happens 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=0$ in the question. If you have further questions on this please refer and calculate the constants yourself. Can this degenerate situation actually happen in a boolean function $f$?
Turbo
<boolean-functions><polynomials>
Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?
Turbo
# Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?

(Asked by: username_0 on 2015-06-05)

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](http://www.cs.huji.ac.il/~noam/degree.ps) 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$?

**Tags:** boolean-functions, polynomials
> **Comments:**
> **username_1**: @Trurbo, I think we have told you a couple of times by now that you should spend more time thinking and formulating your questions _before_ posting them here. It is becoming really annoying that you post a question, people answer what you have posted, and then you say it is not what you are looking for and change question you have asked. I think the frequency of this shows that you don't do your homework before posting your questions.  
> **username_0**: @kaveh please check what happens 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=0$ in the question. If you have further questions on this please refer and calculate the constants yourself. Can this degenerate situation actually happen in a boolean function $f$?  

---

## 1 answers

### Answer by username_2 on 2015-06-05. Score: 4

If I understand correctly you are asking about the relationship between the degree necessary for exact representation and the degree necessary for approximate representation. [The seminal paper by Nisan and Szegedy](http://www.cs.huji.ac.il/~noam/degree.ps) shows that for $\epsilon$ constant these degrees are polynomially related.

> **Comments:**
> **username_0**: sorry I am not asking this. In Nisan-Szegedy, $\lim_{\epsilon\rightarrow\frac{1}2^-}deg_{\epsilon}(f)\geq1$ is best lower bound on degree for a general $f$. My question is could this lower bound depend on $0$-error polynomial degree.  
> **username_0**: Could you remove your answer? It is receiving upvotes and people who may be interested might think this question has a reasonable answer already.  

---

