The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the value of $f$. The sensitivity conjecture, posed by Nisan and Szegedy (CC, 1994), states that the block sensitivity, $bs(f)$, is at most polynomial in the sensitivity, $s(f)$, for any Boolean function $f$. A positive answer to the conjecture will have many consequences, as the block sensitivity is polynomially related to many other complexity measures such as the certificate complexity, the decision tree complexity and the degree. The conjecture is far from being understood, as there is an exponential gap between the known upper and lower bounds relating $bs(f)$ and $s(f)$.

We continue a line of work started by Kenyon and Kutin (Inf. Comput., 2004), studying the $\ell$-block sensitivity, $bs_\ell(f)$, where $\ell$ bounds the size of sensitive blocks. While for $bs_{2}(f)$ the picture is well understood with almost matching upper and lower bounds, for $bs_3(f)$ it is not. We show that any development in understanding $bs_3(f)$ in terms of $s(f)$ will have great implications on the original question. Namely, we show that either $bs(f)$ is at most sub-exponential in $s(f)$ (which improves the state of the art upper bounds) or that $bs_3(f) \ge s(f)^{3-\varepsilon}$ for some Boolean functions (which improves the state of the art separations).

We generalize the question of $bs(f)$ versus $s(f)$ to bounded functions $f:\{0,1\}^n \to [0,1]$ and show an analog result to that of Kenyon and Kutin: $bs_{\ell}(f) = O(s(f))^{\ell}$. Surprisingly, in this case, the bounds are close to being tight. In particular, we construct a bounded function $f:\{0,1\}^n \to [0,1]$ with $bs(f) \ge n/\log n$ and $s(f) = O(\log n)$, a clear counterexample to the sensitivity conjecture for bounded functions.

Finally, we give a new super-quadratic separation between sensitivity and decision tree complexity by constructing Boolean functions with $\mathrm{DT}(f) \ge s(f)^{2.115}$. Prior to this work, only quadratic separations, $\mathrm{DT}(f) = s(f)^2$, were known.