One of the enticing open problems in this area of complexity theory is the sensitivity-block sensitivity conjecture. The best gap between \(\mathsf {bs}(f)\)  and \(\mathsf {s}(f)\)  is quadratic: that is there exists a function \(f\)  such that \(\mathsf {bs}(f) = \Theta (\mathsf {s}(f)^2)\) . The conjecture is that this is indeed tight, that is, for any Boolean function \(f\) , \(\mathsf {bs}(f) = O(\mathsf {s}(f)^2)\) . In the seminal work of [1]} the degree of a Boolean function was bounded by the square of sensitivity, and this is tight for Boolean functions. Since the degree of a Boolean function is quadratically related to the block sensitivity, we have \(\mathsf {bs}(f) \le O(\mathsf {s}(f)^4\) . Unfortunately, this approach via degree will not be able to give any tighter bound on block sensitivity in terms of sensitivity.
