Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
1  
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
2  
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

1 Answer 1

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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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