1
$\begingroup$

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

$\endgroup$
2
  • 5
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Jun 5, 2015 at 19:51
  • $\begingroup$ @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$? $\endgroup$
    – Turbo
    Jun 6, 2015 at 5:04

1 Answer 1

4
$\begingroup$

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 shows that for $\epsilon$ constant these degrees are polynomially related.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Jun 5, 2015 at 19:05
  • $\begingroup$ Could you remove your answer? It is receiving upvotes and people who may be interested might think this question has a reasonable answer already. $\endgroup$
    – Turbo
    Jun 8, 2015 at 10:59

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.