Sensitivity

Definition

Let [math]f: \{-1,1\}^n \to \{-1,1\}[/math] be a Boolean function. The local sensitivity of [math]f[/math] at point [math]x[/math], often denoted [math]s_f(x)[/math], is defined as

[math]s_f(x) = \#\{y \mid f(x) \neq f(y), |x-y|=1 \}.[/math]

In words, it is the number of neighbors of [math]x[/math] on which [math]f[/math] changes its value from [math]f(x)[/math].

The sensitivity of the function [math]f[/math], often denoted [math]s(f)[/math], is the maximum over the local sensitivity:

[math]s(f) = \max \{s_f(x) \mid x \in \{-1,1\}^n \}.[/math]

The local block sensitivity of [math]f[/math] at point [math]x[/math], often denoted [math]bs_f(x)[/math], is defined as

[math]bs_f(x) = \max \#\{t \mid \exists B_1,\ldots,B_t \subseteq [n], B_i \bigcap B_j = \emptyset, f(x) \neq f(x^{\oplus B_i}) \forall i \}.[/math]

Here, [math]x^{\oplus B}[/math] is the vector identical to [math]x[/math], but with every bit in the index set [math]B[/math] flipped. In words, it is the maximal number of disjoint sets of indices that we can find, so that flipping the bits inside a set at once causes the function to change its value.

The block sensitivity of the function [math]f[/math], often denoted [math]bs(f)[/math], is the maximum over the local block sensitivity:

[math]bs(f) = \max \{bs_f(x) \mid x \in \{-1,1\}^n \}.[/math]

Properties

• The expected value of the local sensitivity is equal to the total influence: [math]\mathbb{E}[s_f] = \mathrm{Inf}(f)[/math] .
• The block sensitivity is always larger than the sensitivity: [math]s(f) \leq bs(f)[/math], since we can always take as [math]B_1,\ldots,B_t[/math] the pivotal bits of [math]x[/math].
• The sensitivity and block sensitivity are polynomially related: On one hand, there are functions, such as Rubinstein's sensitivity function where

[math]bs(f) = \Omega(s(f)^2).[/math]

On the other hand, every Boolean function [math]f[/math] satisfies

[math]s(f) = \Omega(bs(f)^4). [/math].