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

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top