Category:Noise sensitive function
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
- ↑ 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.
