1
$\begingroup$

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,1)$ Relations among different boolean approximations

There solution considered $0<\epsilon<\frac{1}{2}\leq\delta<1$. Solution showed relation between $d_{0,f,\epsilon},d_{0,f,\delta}$ is a linear function with constant multiplicative factor as long as we have fixed $\epsilon,\delta$.

This along with solution to another problem in Different boolean degrees polynomially related? shows $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$ holds if we have fixed $\epsilon,\delta$.

(1) I am most interested in case where we have not fixed $\delta$ and/or $\epsilon$. Say $\delta=1-\frac{1}{h(n)}$, $\epsilon=\frac{1}{g(n)}$ (that is either/both $\delta$ or/and $\epsilon$ changes) with some functions $g(n)$, $h(n)$ of $n$ (logarithmic/polynomial/exponential). I am interested in how fast do degrees (multiplicative factors) grow.

(2) There was a comment on sign degree. I understand sign degree is an useful parameter. However for sign degree as I understand ranges of functions involved are over $\Bbb R\backslash\{0\}$ (Only criteria is approximating function takes same sign as $f$). Here ranges are different.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

You're asking several questions. Here are answers for some of them.

  1. The OR function has degree $n$, but it can be approximated by the function $(x_1+\cdots+x_n)/n$. This shows that $d_{1,\text{OR},1-1/n} = 1$.

  2. If you have a polynomial $P$ representing $f$ in the sense that $P(x) = 0$ whenever $f(x) = 0$ and $|P(x)-1|<1$ whenever $f(x) = 1$, then for small enough $\epsilon > 0$, the function $P-\epsilon$ sign-represents $f$.

  3. The correct tradeoff between (say) $d_{0,f,\epsilon}$ and $d_{0,f,\delta}$ for different $\epsilon,\delta$ can be studied using approximation theory, i.e. Chebyshev polynomials and the related Markov and Bernstein theorems and their ilk. The functions converting a $\delta$-approximation to an $\epsilon$-approximation can be constructed explicitly using Chebyshev polynomials, and lower bounds on their degrees can be obtained using Markov–Bernstein theorems. This is similar to the way that the tight bound $\Theta(\sqrt{n})$ for the approximate degree of the OR function $d_{\text{OR},\epsilon}$ is proved.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I strongly suggest you step up and try to read some of the relevant literature on your own this time, and do some of your research yourself. We can help by pointing you to the relevant concepts and techniques, but in the end it's your research and you should be doing it on your own. Your approach of feeding this community with question is akin to the way a supervisor supervises her student, you playing the supervisor's rule. I think a more proper way is for this site to serve as your colleague, you bearing the grunt of the work, us helping you out but not working everything out for you. $\endgroup$
    – Yuval Filmus
    Jan 6, 2015 at 10:54
  • $\begingroup$ $(x_1+\dots+x_n)/n)$ is $1$ if all $x_i$ are $1$. Else it is in $(\frac{1}{n},\frac{n-1}{n})$. I think this is $d_{1,AND,\frac{n-1}{n}}$. Am I correct in that degree of $d_{0,AND,\frac{n-1}{n}}$ seems to be $\Omega(n)$ since polynomial will have to pass through zero at almost every input $(1,1,\dots,1,1)$? $\endgroup$
    – Turbo
    Jan 6, 2015 at 19:56
  • $\begingroup$ $d_{0,AND,\frac{n-1}{n}} = d_{1,NAND,\frac{n-1}{n}}=\Omega(n)$ also seems to be truth. $\endgroup$
    – Turbo
    Jan 6, 2015 at 20:00
  • $\begingroup$ The approximate degree of AND is only $O(\sqrt n) $, and the appreciating function can be arranged to equal 1 exactly at the all ones input. This shows that $d_{1,AND,0.1}=O(\sqrt n) $, for example. $\endgroup$
    – Yuval Filmus
    Jan 6, 2015 at 22:16
  • 1
    $\begingroup$ You're right that $d_{0,AND,1-1/n} = n$. In fact, $d_{0,AND,\epsilon} = n$ for all $\epsilon < 1$, since you can take the approximating function $f$ and normalize it by $f(1,\ldots,1)$ to get a function representing AND exactly, and we already know that this function has degree $n$. $\endgroup$
    – Yuval Filmus
    Jan 7, 2015 at 8:48

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.