<p>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.
(<a href="http://dx.doi.org/10.1007/978-3-662-44602-7_9">http://dx.doi.org/10.1007/978-3-662-44602-7_9</a>)</p>

<p>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.
(<a href="http://www.ieice.org/ken/paper/20131220DBID/eng/">http://www.ieice.org/ken/paper/20131220DBID/eng/</a>)</p>

CC BY-SA 3.0
2014-08-29T17:57:20.607Z
Nice result. I look forward to reading it.
mhum
CC BY-SA 3.0
2014-08-29T09:23:49.910Z
2014-08-29T09:23:49.910Z
Hiroki Morizumi
<p>Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between <span class="math-container">$s(f)$</span> and <span class="math-container">$bs(f)$</span> in order to resolve the conjecture that <span class="math-container">$bs(f)$</span> is only polynomially larger than <span class="math-container">$s(f)$</span>. What about the opposite direction? What is known about functions where <span class="math-container">$s(f) = bs(f)$</span>?</p>
<p>Trivially, constant functions have <span class="math-container">$0=s(f)=bs(f)$</span>. Also trivially, any function with <span class="math-container">$s(f) = n$</span> also has <span class="math-container">$s(f) = bs(f)$</span>. 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 <span class="math-container">$s(f) = bs(f)$</span>? A complete characterization would be ideal. What if we further strengthen the requirements to <span class="math-container">$s^0(f) = bs^0(f)$</span> and <span class="math-container">$s^1(f) = bs^1(f)$</span>?</p>
<p>The motivation for this question is simply to get some intuition for how sensitivity relates to block sensitivity.</p>
<h2>Definitions</h2>
<p>Let <span class="math-container">$f:\{0,1\}^n\rightarrow \{0,1\}$</span> be a Boolean function on <span class="math-container">$n$</span>-bit words. For <span class="math-container">$x \in \{0,1\}^n$</span> and <span class="math-container">$A \subseteq \{1,\ldots,n\}$</span>, let <span class="math-container">$x^A$</span> denote the <span class="math-container">$n$</span>-bit word obtained from <span class="math-container">$x$</span> by flipping the bits specified by <span class="math-container">$A$</span>. In the case that <span class="math-container">$A = \{i\}$</span>, we will simply denote this as <span class="math-container">$x^i$</span>.</p>
<p>We define the <em>sensitivity of <span class="math-container">$f$</span> at <span class="math-container">$x$</span></em> as <span class="math-container">$s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$</span>. In other words, it is the number of bits in <span class="math-container">$x$</span> that we can flip in order to flip the output of <span class="math-container">$f$</span>. We define the <em>sensitivity</em> of <span class="math-container">$f$</span> as <span class="math-container">$s(f) = \text{max}_x s(f,x)$</span>.</p>
<p>We define the <em>block sensitivity of <span class="math-container">$f$</span> at <span class="math-container">$x$</span></em> (denoted <span class="math-container">$bs(f,x)$</span>) as the maximum <span class="math-container">$k$</span> such that there are disjoint subsets <span class="math-container">$B_1, B_2, \ldots, B_k$</span> of <span class="math-container">$\{1,2,\ldots, n\}$</span> such that <span class="math-container">$f(x^{B_i}) \neq f(x)$</span>. We define the <em>block sensitivity</em> of <span class="math-container">$f$</span> as <span class="math-container">$bs(f) = \text{max}_x bs(f,x)$</span>.</p>
<p>Finally, we define the <em>0-sensitivity</em> of <span class="math-container">$f$</span> as <span class="math-container">$s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$</span>. We similarly define <em>1-sensitivity</em>, <em>0-block sensitivity</em>, and <em>1-block sensitivity</em> , denoted <span class="math-container">$s^1(f)$</span>, <span class="math-container">$bs^0(f)$</span>, and <span class="math-container">$bs^1(f)$</span>, respectively.</p>

CC BY-SA 4.0
2020-11-24T20:37:59.633Z
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?
Andrew Kelley
CC BY-SA 4.0
2020-11-24T20:53:28.177Z
@AndrewKelley Ah yes, good catch. I'll make the edit
mhum
<circuit-complexity><boolean-functions>
Boolean Functions Where Sensitivity Equals Block Sensitivity
mhum
# Boolean Functions Where Sensitivity Equals Block Sensitivity

(Asked by: username_0 on 2013-11-21)

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.

**Tags:** circuit-complexity, boolean-functions

> **Comments:**
> **username_1**: 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?  
> **username_0**: @AndrewKelley Ah yes, good catch. I'll make the edit  

---

## 1 answers

### Answer by username_2 on 2014-08-29. Score: 19 | Accepted answer

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/>)

> **Comments:**
> **username_0**: Nice result. I look forward to reading it.  

---

