# Boolean Functions Where Sensitivity Equals Block Sensitivity

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.

## Definitions

Let $$f:\{0,1\}^n\rightarrow \{0,1\}$$ be a Boolean function on $$n$$-bit words. For $$x \in \{0,1\}^n$$ and $$A \subseteq \{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.

• Shouldn't $A$ be a subset of either $\{1, \ldots, n \}$ or $\{0, \ldots, n - 1 \}$, depending on whether we are 1-indexing or 0-indexing? Nov 24, 2020 at 20:37
• @AndrewKelley Ah yes, good catch. I'll make the edit
– mhum
Nov 24, 2020 at 20:53