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