Sensitivity

Definition

Let [math]f[/math] be a Boolean function. The local sensitivity of [math]f: \{-1,1\}^n \to \{-1,1\}[/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]

Properties

• The expected value of the local sensitivity is equal to the total influence: [math]\mathbb{E}[s_f] = \mathrm{Inf}(f)[/math] .