Sensitivity

Definition

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

 $s_f(x) = \#\{y \mid f(x) \neq f(y), |x-y|=1 \}.$

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

The sensitivity of the function $f$, often denoted $s(f)$, is the maximum over the local sensitivity:

 $s(f) = \max \{s_f(x) \mid x \in \{-1,1\}^n \}.$

Properties

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

References

1. Ryan O'Donnell, Analysis of Boolean functions, Proposition 27 in section 2.3