# Upperbound on the degree of a boolean function in terms of its sensitivity

A very interesting open problem in the study of complexity measures of Boolean function is the so called sensitivity vs block sensitivity conjecture. For background on sensitivity versus block sensitivity you can look at the following blogpost of S. Aaronson at http://www.scottaaronson.com/blog/?p=453.

To best of my knowledge, the best upper bound known on $bs(f)$ in terms of $s(f)$ is $bs(f)=O(e^{s(f)}\sqrt{s(f)})$. [Kenyon, Kutin paper] But of course maybe it is more convenient to relate $s(f)$ to some other complexity measure of $f$ say $\deg(f)$, the degree of $f$ as polynomial over $\mathbb{R}$, i.e. the size of its highest Fourier coefficient.

The question is what's the best upper bound known on $\deg(f)$ in terms of $s(f)$?

• You can use Nisan-Szegedy's result that the deterministic decision tree complexity is $D(f)\leq bs^4(f)$ and you'll have $\widetilde{deg}(f)=O(e^{4s(f)} s^2(f))$. I don't know if this is best though. – Marcos Villagra Dec 11 '12 at 0:54
• I'm fairly confident that no one has done better than via the connection Marcos mentions. It's most natural to relate s to bs. deg(f) is polynomially related to most other quantities, e.g. D(f), bs(f), C(f), approx-deg(f), etc. You may enjoy the Buhrman-De Wolf survey on decision tree complexity which reviews these measures. – Andy Drucker Dec 14 '12 at 4:24
• I think Simon proof from the 80's give a slightly better bound: something like $deg(f) \le DT(f) \le 4^{s(f)}\cdot poly(s(f))$. – Avishay Tal Jan 10 '13 at 22:23

This paper came up on the arXiv today and it improves on the upper bound on $bs(f)$ in terms of $s(f)$. They prove the following bound:
$$bs(f) \leq 2^{s(f)-1}s(f).$$