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?

  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jan 5 '15 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.

  • $\begingroup$ 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). $\endgroup$ – Bread Winner Jan 1 '15 at 11:15
  • $\begingroup$ If you have a different question you're welcome to ask it separately. $\endgroup$ – Yuval Filmus Jan 1 '15 at 11:19
  • $\begingroup$ What is symbol $O_\epsilon$ represent? $\endgroup$ – Bread Winner Jan 3 '15 at 5:41
  • $\begingroup$ Also theorem $3$ talks about quantum algorithm. Is there a reference with classical algorithm that talks about the bound mentioned there? $\endgroup$ – Bread Winner Jan 3 '15 at 6:04
  • 1
    $\begingroup$ (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. $\endgroup$ – Yuval Filmus Jan 3 '15 at 18:52

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.