patternMinor
Sensitivity and Block sensitivity
Viewed 0 times
sensitivityblockand
Problem
May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity.
Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.
Let $[n]=\{1,2,\dots,n\}$.
If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.
If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.
If $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.
If $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.
Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$
Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$
Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$
Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$
It is clear that $S(f)\leq BS(f)$ since we can take size $1$ blocks at coordinates of input $x$ that are modified to achieves $S(f)$.
So why can't I say $BS(f)\leq S(f)$? That is, suppose we found a maximum set of blocks $B_i$ that are disjoint, then cant I say:
-
There is no other bit position outside of $\cup_{i=1}^rB_i$ where we can change an input in order to change the input (Or else there is a size $1$ block that is disjoint and we can add to list $B_i$ incrasing $r$).
-
It is clear $S(f) = |\cup_{i=1}^rB_i|$ since if we change all bit positions in $B_i$ we change inputs and there is no other extra bit position by $1$.
-
Split the $B_i$ in to size $1$ blocks to get $S(f)=BS(f)$?
Am I wrong in the definition that $2$ DOES NOT HOLD since we can only consider $1$ block at a time and hence we can only say $S(f)\geq max_i|B_i|$? Anything else I am missing?
Is there any example for which $BS(f)\leq S(f)^{1+\epsilon}$?
Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.
Let $[n]=\{1,2,\dots,n\}$.
If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.
If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.
If $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.
If $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.
Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$
Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$
Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$
Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$
It is clear that $S(f)\leq BS(f)$ since we can take size $1$ blocks at coordinates of input $x$ that are modified to achieves $S(f)$.
So why can't I say $BS(f)\leq S(f)$? That is, suppose we found a maximum set of blocks $B_i$ that are disjoint, then cant I say:
-
There is no other bit position outside of $\cup_{i=1}^rB_i$ where we can change an input in order to change the input (Or else there is a size $1$ block that is disjoint and we can add to list $B_i$ incrasing $r$).
-
It is clear $S(f) = |\cup_{i=1}^rB_i|$ since if we change all bit positions in $B_i$ we change inputs and there is no other extra bit position by $1$.
-
Split the $B_i$ in to size $1$ blocks to get $S(f)=BS(f)$?
Am I wrong in the definition that $2$ DOES NOT HOLD since we can only consider $1$ block at a time and hence we can only say $S(f)\geq max_i|B_i|$? Anything else I am missing?
Is there any example for which $BS(f)\leq S(f)^{1+\epsilon}$?
Solution
2 does not hold as stated. All you know is that if you flip the all bits in a given block $B_i$, the output flips. Without additional conditions, I don't think you're guaranteed anything about flipping any individual bit within $B_i$.
EDIT: In fact, if $B_1, B_2, \ldots, B_i, \ldots$ represents a maximal set of blocks, then for any $B_i$, there cannot be more than one index within $B_i$ such that flipping the bit at that index will flip the output. Suppose that within $B_i$ there are two indices, say $j$ and $k$, such that flipping either $x_j$ or $x_k$ will flip the output. Then $B_i$ can be replaced by the two singletons $j$ and $k$, thus contradicting the assumption that the set of blocks was maximal.
Meanwhile, the first function found to have a quadratic gap between $BS(f)$ and $S(f)$ is due to Rubinstein (1995). You can find a quick summary of the construction in this blog post by Scott Aaronson. A function with slightly bigger separation was found later by Virza (2011).
EDIT: In fact, if $B_1, B_2, \ldots, B_i, \ldots$ represents a maximal set of blocks, then for any $B_i$, there cannot be more than one index within $B_i$ such that flipping the bit at that index will flip the output. Suppose that within $B_i$ there are two indices, say $j$ and $k$, such that flipping either $x_j$ or $x_k$ will flip the output. Then $B_i$ can be replaced by the two singletons $j$ and $k$, thus contradicting the assumption that the set of blocks was maximal.
Meanwhile, the first function found to have a quadratic gap between $BS(f)$ and $S(f)$ is due to Rubinstein (1995). You can find a quick summary of the construction in this blog post by Scott Aaronson. A function with slightly bigger separation was found later by Virza (2011).
Context
StackExchange Computer Science Q#33798, answer score: 4
Revisions (0)
No revisions yet.