# Deterministic query complexity and polynomial degree

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?

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).
• 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 – Swagato Nov 21 '15 at 6:43