Noise sensitivity
Revision as of 09:50, 23 September 2019 by Or elmackias (talk | contribs) (Created page with "== Definition == For <math>f:\{-1,1\}^{n}\longrightarrow\{-1,1\}</math> and <math>\delta\in[0,1]</math>, the noise sensitivity of <math>f</math> at <math>\delta</math>, <math...")
Definition
For [math]f:\{-1,1\}^{n}\longrightarrow\{-1,1\}[/math] and [math]\delta\in[0,1][/math], the noise sensitivity of [math]f[/math] at [math]\delta[/math], [math]NS_{\delta}[f][/math], is the probability that [math]f(x)\neq f(y)[/math] when [math]x\sim\{-1,1\}^{n}[/math] is uniformly random and [math]y[/math] is formed from [math]x[/math] by reversing each bit independently with probability [math]\delta[/math].
