2
$\begingroup$

What is the current best upper bound known on deterministic decision tree complexity of a Boolean function in terms of its polynomial degree? Also, what is the current widest separation known between these two measures?

$\endgroup$
1
$\begingroup$

According to Table 2 in Aaronson, Ben-David and Kothari, the best separation between degree $\deg f$ and decision tree complexity $D(f)$ is $D(f) = \Omega(\deg f)^2)$, achieved by Göös, Pitassi and Watson, and the best upper bound is $D(f) = O((\deg f)^3)$ (perhaps already from the classic work of Nisan and Szegedy).

$\endgroup$
  • 1
    $\begingroup$ Thank you. I think you meant $$D(f)=\Omega((deg(f))^2)$$ in the separation statement. Also, I asked around and found the following paper that proves the cubic upper bound that you mentioned (which is a tightening of the Nisan-Smolensky 4th power upper bound proof). arxiv.org/pdf/quant-ph/0403168.pdf $\endgroup$ – Swagato Nov 21 '15 at 6:43

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.