0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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, 2015 at 1:33

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\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$
    – Turbo
    Jan 1, 2015 at 11:15
  • $\begingroup$ If you have a different question you're welcome to ask it separately. $\endgroup$
    – Yuval Filmus
    Jan 1, 2015 at 11:19
  • $\begingroup$ What is symbol $O_\epsilon$ represent? $\endgroup$
    – Turbo
    Jan 3, 2015 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$
    – Turbo
    Jan 3, 2015 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, 2015 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.