Difference between revisions of "Sensitivity"
(Created page.) |
m |
||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
| − | Let <math>f</math> be a Boolean function. The '''local sensitivity''' of <math>f | + | 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 |
:::{| class="wikitable" | :::{| class="wikitable" | ||
|- | |- | ||
Revision as of 17:46, 2 March 2020
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]
Properties
- The expected value of the local sensitivity is equal to the total influence: [math]\mathbb{E}[s_f] = \mathrm{Inf}(f)[/math] [1].
References
- ↑ Ryan O'Donnell, Analysis of Boolean functions, Proposition 27 in section 2.3
