Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ is only polynomially larger than $s(f)$. What about the opposite direction? What is known about functions where $s(f) = bs(f)$?Trivially, constant functions have $0=s(f)=bs(f)$. Also trivially, any function with $s(f) = n$ also has $s(f) = bs(f)$. It is non-trivial but not too hard to show that any monotone function also satisfies this equality. Are there any other nice classes of functions that have $s(f) = bs(f)$? A complete characterization would be ideal. What if we further strengthen the requirements to $s^0(f) = bs^0(f)$ and $s^1(f) = bs^1(f)$? The motivation for this question is simply to get some intuition for how sensitivity relates to block sensitivity. DefinitionsLet $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function on $n$-bit words. For $x \in \{0,1\}$ and $A \subseteq \{0,1,\ldots,n\}$, let $x^A$ denote the $n$-bit word obtained from $x$ by flipping the bits specified by $A$. In the case that $A = \{i\}$, we will simply denote this as $x^i$. We define the sensitivity of $f$ at $x$ as $s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$. In other words, it is the number of bits in $x$ that we can flip in order to flip the output of $f$. We define the sensitivity of $f$ as $s(f) = \text{max}_x s(f,x)$.  We define the block sensitivity of $f$ at $x$ (denoted $bs(f,x)$) as the maximum $k$ such that there are disjoint subsets $B_1, B_2, \ldots, B_k$ of $\{1,2,\ldots, n\}$ such that $f(x^{B_i}) \neq f(x)$. We define the block sensitivity of $f$ as $bs(f) = \text{max}_x bs(f,x)$.Finally, we define the 0-sensitivity of $f$ as $s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$. We similarly define 1-sensitivity, 0-block sensitivity, and 1-block sensitivity , denoted $s^1(f)$, $bs^0(f)$, and $bs^1(f)$, respectively.
Boolean Functions Where Sensitivity Equals Block Sensitivity
circuit complexity;boolean functions
Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014.(http://dx.doi.org/10.1007/978-3-662-44602-7_9)You may be attacking this problem. If so, I feel sorry, but I started to attack the problem independently before the question was posted. A preliminary version of my paper was presented at a Japanese domestic meeting in Dec/2013 and the submission deadline was Oct/2013.(http://www.ieice.org/ken/paper/20131220DBID/eng/)