Difference between revisions of "Sensitivity"
(Created page.) |
|||
| (3 intermediate revisions by the same user not shown) | |||
| 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" | ||
|- | |- | ||
| Line 13: | Line 13: | ||
|} | |} | ||
| + | The '''1-sensitivity''' of the function <math>f</math>, often denoted <math>s_1(f)</math>, is the maximum over local sensitivity for values for which <math>f = 1</math>: | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math>s_1(f) = \max \{s_f(x) \mid x \in \{-1,1\}^n, f(x) = 1 \}.</math> | ||
| + | |} | ||
| + | The '''0-sensitivity''' or '''(-1)-sensitivity''' is defined similarly. | ||
| + | |||
| + | The '''local block sensitivity''' of <math>f</math> at point <math>x</math>, often denoted <math>bs_f(x)</math>, is defined as | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<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: | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math>bs(f) = \max \{bs_f(x) \mid x \in \{-1,1\}^n \}.</math> | ||
| + | |} | ||
== Properties == | == Properties == | ||
* The expected value of the local sensitivity is equal to the total [[influence]]: <math>\mathbb{E}[s_f] = \mathrm{Inf}(f)</math> <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=368 Proposition 27 in section 2.3]</ref>. | * The expected value of the local sensitivity is equal to the total [[influence]]: <math>\mathbb{E}[s_f] = \mathrm{Inf}(f)</math> <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=368 Proposition 27 in section 2.3]</ref>. | ||
| + | * 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 | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math>bs(f) = \Omega(s(f)^2).</math> | ||
| + | |} On the other hand, every Boolean function <math>f</math> satisfies | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math>s(f) = \Omega(bs(f)^4). | ||
| + | </math><ref>Theorem 1.5 in [https://arxiv.org/pdf/1907.00847.pdf Induced subgraphs of hypercubes anda proof of the Sensitivity Conjecture] by Hao Huang (2019)</ref>. | ||
| + | |} | ||
== References == | == References == | ||
<references/> | <references/> | ||
Latest revision as of 06:56, 17 March 2021
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 1-sensitivity of the function [math]f[/math], often denoted [math]s_1(f)[/math], is the maximum over local sensitivity for values for which [math]f = 1[/math]:
[math]s_1(f) = \max \{s_f(x) \mid x \in \{-1,1\}^n, f(x) = 1 \}.[/math]
The 0-sensitivity or (-1)-sensitivity is defined similarly.
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] [1].
- 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
On the other hand, every Boolean function [math]f[/math] satisfies[math]bs(f) = \Omega(s(f)^2).[/math]
[math]s(f) = \Omega(bs(f)^4). [/math][2].
References
- ↑ Ryan O'Donnell, Analysis of Boolean functions, Proposition 27 in section 2.3
- ↑ Theorem 1.5 in Induced subgraphs of hypercubes anda proof of the Sensitivity Conjecture by Hao Huang (2019)
