# Different boolean degrees polynomially related?

Let $f$ be a Boolean function.

Let $p$ be the minimum degree real polynomial that represents $f$ with degree $d_f$.

Let $p_\epsilon$ be the minimum degree real polynomial with degree $d_{f,\epsilon}$ such that $$|p_\epsilon(x)-f(x)|\leq\epsilon.$$

Let $p_{0,\epsilon}$ be the minimum degree real polynomial with degree $d_{0,f,\epsilon}$ 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 real polynomial with degree $d_{1,f,\epsilon}$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Are $d_f,d_{f,\epsilon},d_{0,f,\epsilon}$ and $d_{1,f,\epsilon}$ all polynomially related? It is clear $$d_{f,\epsilon}\leq d_{0,f,\epsilon},d_{1,f,\epsilon}\leq d_f.$$

Does $$d_{f}\leq (d_{0,f,\epsilon})^a,(d_{1,f,\epsilon})^b\leq (d_{f,\epsilon})^c$$ hold for some $a,b,c\in\Bbb N$?

What is a good reference to understand relations among these four degrees?

• I can't understand your question. 1. I'm already lost at your second sentence, which says "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$? 2. What variables are given? 3. Why is this a CS question, as opposed to a pure math question? Would you like to elaborate on why this is suitable for CS.SE? We expect you to make these connections explicit in the question. See e.g., meta.cs.stackexchange.com/q/704/755.
– D.W.
Jan 5, 2015 at 1:33

It is known that $$d_f = O_\epsilon(d_{f,\epsilon}^6),$$ for all $\epsilon < 1/2$. This is described in many lecture notes, for example these quantum lecture notes by Montanaro (Theorem 3). It is suspected that the best exponent is $2$. It is known that the exact value of $\epsilon$ only affects the constant.
Since $d_{f,\epsilon} \leq d_{0,f,\epsilon},d_{1,f,\epsilon} \leq d_f$, the other measures are also polynomially related.
• This does not explain the question here though cstheory.stackexchange.com/questions/28016/… Here I want to consider arguments as integers. If it is just parity function, I can use the argument you gave. What if we need to compute $n\bmod 2$ where $n$ is an integer (technically $\bmod2$ value depends on just the last bit in total). Jan 1, 2015 at 11:15
• What is symbol $O_\epsilon$ represent? Jan 3, 2015 at 5:41
• Also theorem $3$ talks about quantum algorithm. Is there a reference with classical algorithm that talks about the bound mentioned there? Jan 3, 2015 at 6:04
• (1) The symbol $O_\epsilon$ signifies that the hidden constant depends on $\epsilon$. (2) Theorem 3 talks about quantum algorithm, but if you look at the proof, it's all about polynomials. You can also search for alternative proofs online. The paper by Nisan and Szegedy proves that $d_f = O_\epsilon(d_{f,\epsilon}^8)$, using almost the same argument. Jan 3, 2015 at 18:52