11
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – Marcos Villagra
    Commented Dec 11, 2012 at 0:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andy Drucker
    Commented Dec 14, 2012 at 4:24
  • 2
    $\begingroup$ 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))$. $\endgroup$
    – Avishay Tal
    Commented Jan 10, 2013 at 22:23

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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