Difference between revisions of "Category:Noise stable 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 stable''' if <math>\lim_{\delta \to 0} \sup_n \mathbb{P}\left | + | A series of functions <math>f_n:\{-1,1\}^n \to \{-1,1\}</math> is said to be '''noise stable''' if |
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<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. | ||
Latest revision as of 14:55, 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 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
Pages in category "Noise stable function"
The following 3 pages are in this category, out of 3 total.
