Difference between revisions of "Category:Noise sensitive function"
(Created page with "== Definition == Let <math>\delta > 0</math>. Two <math>n</math>-bit vectors <math>x</math> and <math>y</math> are said to be <math>\delta</math>-correlated, if they are both...") |
m |
||
| Line 3: | Line 3: | ||
Let <math>\delta > 0</math>. Two <math>n</math>-bit vectors <math>x</math> and <math>y</math> are said to be <math>\delta</math>-correlated, if they are both uniform on the hypercube, and each bit <math>x_i</math> is <math>\delta</math>-correlated with <math>y_i</math>. Such pairs can be constructed, for example, by picking <math>x</math> uniformly at random, and having <math>y</math> be a copy of <math>x</math>, but where every bit is independentally resampled with probability <math>\delta</math>. | Let <math>\delta > 0</math>. Two <math>n</math>-bit vectors <math>x</math> and <math>y</math> are said to be <math>\delta</math>-correlated, if they are both uniform on the hypercube, and each bit <math>x_i</math> is <math>\delta</math>-correlated with <math>y_i</math>. Such pairs can be constructed, for example, by picking <math>x</math> uniformly at random, and having <math>y</math> be a copy of <math>x</math>, but where every bit is independentally resampled with probability <math>\delta</math>. | ||
| − | A series of functions <math>f_n:\{-1,1\}^n \to \{-1,1\}</math> is said to be '''noise sensitive''' if for every <math>\delta>0</math>, <math>\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 | + | A series of functions <math>f_n:\{-1,1\}^n \to \{-1,1\}</math> is said to be '''noise sensitive''' if for every <math>\delta>0</math>, |
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math>\lim_{n \to \infty} \mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 = 0</math>, | ||
| + | |} | ||
| + | |||
| + | where <math>x</math> and <math>y</math> are <math>\delta</math>-correlated,. | ||
Latest revision as of 14:56, 7 April 2021
Definition
Let [math]\delta \gt 0[/math]. Two [math]n[/math]-bit vectors [math]x[/math] and [math]y[/math] are said to be [math]\delta[/math]-correlated, if they are both uniform on the hypercube, and each bit [math]x_i[/math] is [math]\delta[/math]-correlated with [math]y_i[/math]. Such pairs can be constructed, for example, by picking [math]x[/math] uniformly at random, and having [math]y[/math] be a copy of [math]x[/math], but where every bit is independentally resampled with probability [math]\delta[/math].
A series of functions [math]f_n:\{-1,1\}^n \to \{-1,1\}[/math] is said to be noise sensitive if for every [math]\delta\gt 0[/math],
[math]\lim_{n \to \infty} \mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 = 0[/math],
where [math]x[/math] and [math]y[/math] are [math]\delta[/math]-correlated,.
Properties
- The BKS theorem relates the influences of a function to noise-sensitivity: If [math]\sum_k \mathrm{Inf}_k(f_n)^2 \to 0[/math], then [math]f_n[/math] is noise-sensitive. [1]
References
- Jump up ↑ Theorem 1.3 in "Noise sensitivity of Boolean functions and applications to percolation" by Itai Benjamini, Gil Kalai and Oded Schramm.
Pages in category "Noise sensitive function"
The following 6 pages are in this category, out of 6 total.
