5
$\begingroup$

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:

  1. 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$).

  2. 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$.

  3. 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}$?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "...., there cannot be more than one index within Bi such that flipping the bit at that index will flip the output." I suppose this comment is for some input $x$. If the input changes then this bit position that needs to be flipped cab change. Correct? $\endgroup$ – T.... Dec 5 '14 at 7:18
  • 1
    $\begingroup$ But if the input changes, then the set of blocks may also need to change (to preserve maximality), leaving you pretty much where you started. Maximality in this context only makes sense with respect to a specific input (i.e.: not all inputs). $\endgroup$ – mhum Dec 5 '14 at 17:36
3
$\begingroup$

Virza, improving on earlier work of Rubinstein, gives a function on $(2k+1)^2$ variables with sensitivity $2k+1$ and block sensitivity $(2k+1)(k+1)$. His function is defined as follows. Partition the input variables into $2k+1$ "sections" of size $2k+1$. The function is 1 if at least one section $x_1,\ldots,x_{2k+1}$ satisfies one of the following: (1) $x_{2i-1} = x_{2i} = 1$ for some $1 \leq i \leq k$ and all other $x_j$ are zero, or (2) $x_{2k+1} = 1$ and all other $x_j$ are zero.

$\endgroup$
  • $\begingroup$ arxiv.org/pdf/1108.3494v1.pdf also improves known results? $\endgroup$ – T.... Dec 4 '14 at 9:43
  • $\begingroup$ Right, the paper you mention gives even better results. $\endgroup$ – Yuval Filmus Dec 4 '14 at 15:31

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.