<p><a href="http://arxiv.org/abs/1306.4466">This paper</a> 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:</p>

<p>$$
bs(f) \leq 2^{s(f)-1}s(f).
$$</p>

<p>This along with the connection that Marcos mentioned in his comment should give better bounds than previously known.</p>

CC BY-SA 3.0
2013-06-20T01:05:44.930Z
2013-06-20T01:13:10.233Z
2013-06-20T01:13:10.233Z
Alessandro Cosentino
<p>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 <a href="http://www.scottaaronson.com/blog/?p=453">http://www.scottaaronson.com/blog/?p=453</a>.</p>

<p>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. </p>

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

CC BY-SA 3.0
2012-12-11T00:54:32.677Z
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
CC BY-SA 3.0
2012-12-14T04:24:07.100Z
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
CC BY-SA 3.0
2013-01-10T22:23:56.670Z
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
<cc.complexity-theory><reference-request><fourier-analysis>
Upperbound on the degree of a boolean function in terms of its sensitivity
Mohammad Bavarian
# Upperbound on the degree of a boolean function in terms of its sensitivity

(Asked by: username_0 on 2012-12-09)

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)$?

**Tags:** cc.complexity-theory, reference-request, fourier-analysis

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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))$.  

---

## 1 answers

### Answer by username_4 on 2013-06-20. Score: 9

[This paper](http://arxiv.org/abs/1306.4466) 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).
$$

This along with the connection that Marcos mentioned in his comment should give better bounds than previously known.


---

