13
$\begingroup$

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\}$ 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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Nice result. I look forward to reading it. $\endgroup$ – mhum Aug 29 '14 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.