Category:Noise stable 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 stable if

[math]\lim_{\delta \to 0} \sup_n \mathbb{P}\left[f_n(x) \neq f_n(y) \right] =0[/math],

where [math]x[/math] and [math]y[/math] are [math]\delta[/math]-correlated.

Properties

• None yet.

References