For every \(n\in \mathbb N\), \(f:\{ 0,1\} ^{n}\to \mathbb R\) and real \(\rho \geq 0\), the noise stability

is nonnegative, where \(\widehat f(S)=2^{-n}\sum _{x\in \{ 0,1\} ^{n}}f(x)\prod _{i\in S}(-1)^{x_i}\) is the normalized Walsh coefficient (and \(\rho ^0=1\), including at \(\rho =0\)).

For every \(n\in \mathbb N\), real-valued \(f:\{ 0,1\} ^{n}\to \mathbb R\) and real \(\delta \leq 1/2\), including negative \(\delta \), the total real-valued noise sensitivity satisfies

where \(\widehat f(S)=2^{-n}\sum _{x\in \{ 0,1\} ^{n}}f(x)\prod _{i\in S}(-1)^{x_i}\).

For every real \(\delta \) with \(0\lt \delta \leq 1/2\), the natural number \(m=\lfloor 1/\delta \rfloor \) satisfies

For every real \(\delta \) with \(0\lt \delta \leq 1/2\), setting \(m=\lfloor 1/\delta \rfloor \) gives

Let \(B=(B_n)_{n\in \mathbb N}\) be a family of sets of functions \(\{ 0,1\} ^{n}\to \{ -1,1\} \) and let \(\varepsilon :\mathbb R\to \mathbb R\) satisfy \(\varepsilon (\delta )\geq 0\) for \(0\leq \delta \leq 1/2\), \(\lim _{\delta \to 0^{+}}\varepsilon (\delta )=0\) and \(\operatorname {NS}_{\delta }(f)\leq \varepsilon (\delta )\) for every \(n\), \(f\in B_n\) and \(0\lt \delta \leq 1/2\). Then \(B\) is uniformly noise-stable: there exists \(\eta :\mathbb R\to \mathbb R\) with \(0\leq \eta (\delta )\leq 1\) on \([0,1/2]\), \(\lim _{\delta \to 0^{+}}\eta (\delta )=0\) and \(\operatorname {NS}_{\delta }(f)\leq \eta (\delta )\) for every such \(n,f,\delta \), where \(\operatorname {NS}_{\delta }(f)=\Pr [f(X)\neq f(Y)]\), \(X\) is uniform on the cube and \(Y\) flips each coordinate independently with probability \(\delta \).

For every \(n\in \mathbb N\), every member \(f\) of the linear threshold class on \(\{ 0,1\} ^{n}\) takes values in \(\{ -1,1\} \); the class consists of functions \(f(x)=\operatorname {sgn}_{+}(c+\sum _{i=1}^{n}a_i(-1)^{x_i})\) with real coefficients, where \(\operatorname {sgn}_{+}(t)=1\) for \(t\geq 0\) and \(-1\) for \(t\lt 0\).

For all \(n,m\in \mathbb N\), real coefficients \(c,a_1,\ldots ,a_n\), \(z\in \{ 0,1\} ^{n}\) and maps \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \), if \(f(x)=\operatorname {sgn}_{+}(c+\sum _{i=1}^{n}a_i(-1)^{x_i})\), then \(g(w)=f((z_i+w_{\pi (i)}\pmod2)_{i=1}^{n})\) is a \(\{ -1,1\} \)-valued linear threshold function on \(\{ 0,1\} ^{m}\), meaning that \(g(w)=\operatorname {sgn}_{+}(b+\sum _{j=1}^{m}u_j(-1)^{w_j})\) for some real \(b,u_1,\ldots ,u_m\). Here \(\operatorname {sgn}_{+}(t)=1\) for \(t\geq 0\) and \(-1\) for \(t\lt 0\).

For all \(n,m\in \mathbb N\), maps \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \) and subsets \(S\subseteq \{ 1,\ldots ,n\} \), the set \(O_{\pi }(S)=\{ j\in \{ 1,\ldots ,m\} :|\{ i\in S:\pi (i)=j\} |\text{ is odd}\} \) satisfies \(|O_{\pi }(S)|\leq |S|\).

For every bit \(b\in \{ 0,1\} \) and natural number \(c\), setting \(s(b)=(-1)^b\) gives

For \(n,m\in \mathbb N\), a map \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \), \(S\subseteq \{ 1,\ldots ,n\} \) and \(w\in \{ 0,1\} ^{m}\), set \(O_{\pi }(S)=\{ j\in \{ 1,\ldots ,m\} :|\{ i\in S:\pi (i)=j\} |\text{ is odd}\} \); then

For \(n,m\in \mathbb N\), \(z\in \{ 0,1\} ^{n}\), \(w\in \{ 0,1\} ^{m}\), a map \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \) and \(S\subseteq \{ 1,\ldots ,n\} \), define \(\chi _A(x)=\prod _{i\in A}(-1)^{x_i}\) for subsets of the coordinate set of \(x\), and set \(O_{\pi }(S)=\{ j\in \{ 1,\ldots ,m\} :|\{ i\in S:\pi (i)=j\} |\text{ is odd}\} \); then

For every \(k,n,m\in \mathbb N\), a function \(f:\{ 0,1\} ^{n}\to \{ -1,1\} \) of the form \(f(x)=\operatorname {sgn}_{+}(p((-1)^{x_1},\ldots ,(-1)^{x_n}))\) for a real multilinear polynomial \(p\) of degree at most \(k\), every \(z\in \{ 0,1\} ^{n}\) and every map \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \), the function \(g(w)=f((z_i+w_{\pi (i)}\pmod2)_{i=1}^{n})\) is also \(\{ -1,1\} \)-valued and has a representation \(g(w)=\operatorname {sgn}_{+}(q((-1)^{w_1},\ldots ,(-1)^{w_m}))\) with a real multilinear polynomial \(q\) of degree at most \(k\). Here \(\operatorname {sgn}_{+}(t)=1\) for \(t\geq 0\) and \(-1\) for \(t\lt 0\).

For every \(n,k,k'\in \mathbb N\) with \(k\leq k'\), every \(\{ -1,1\} \)-valued function on \(\{ 0,1\} ^{n}\) represented by \(\operatorname {sgn}_{+}(p((-1)^{x_1},\ldots ,(-1)^{x_n}))\) for a real multilinear polynomial \(p\) of degree at most \(k\) also admits such a representation of degree at most \(k'\), where \(\operatorname {sgn}_{+}(t)=1\) for \(t\geq 0\) and \(-1\) for \(t\lt 0\).

For every \(n,m\in \mathbb N\), \(f:\{ 0,1\} ^{n}\to \mathbb R\), \(z\in \{ 0,1\} ^{n}\), \(w\in \{ 0,1\} ^{m}\) and map \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \), define \(g(v)=f((u_i(v))_{i=1}^{n})\), where \(u_i(v)=1-v_{\pi (i)}\) when \(z_i=1\) and \(u_i(v)=v_{\pi (i)}\) when \(z_i=0\); then

where \(\oplus \) is coordinatewise addition modulo \(2\).

For \(n,m\in \mathbb N\), \(f:\{ 0,1\} ^{n}\to \mathbb R\), \(z\in \{ 0,1\} ^{n}\), a map \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \), \(w\in \{ 0,1\} ^{m}\) and \(j\in \{ 1,\ldots ,m\} \), define \(g(v)=f(z\oplus (v_{\pi (i)})_{i=1}^{n})\), where \(\oplus \) is coordinatewise addition modulo \(2\), and write \(x^{A}\) for the vector obtained by flipping precisely the coordinates in \(A\); then

For \(n,m\in \mathbb N\), \(f:\{ 0,1\} ^{n}\to \mathbb R\), a map \(\pi :\{ 1,\ldots ,n\} \to \{ 1,\ldots ,m\} \) and \(j\in \{ 1,\ldots ,m\} \), define \(g_z(w)=f(z\oplus (w_{\pi (i)})_{i=1}^{n})\), where \(\oplus \) is coordinatewise addition modulo \(2\), and write \(x^{A}\) for the vector obtained by flipping the coordinates in \(A\); then

Each expectation is uniform on the full Boolean cube of its variable’s dimension.

For every \(n\in \mathbb N\), positive integer \(m\), \(f:\{ 0,1\} ^{n}\to \{ -1,1\} \) and \(j\in \{ 1,\ldots ,m\} \),

Here \(X\) is uniform on \(\{ 0,1\} ^{n}\), \(X^{A}\) flips precisely the coordinates of \(A\), and \(\operatorname {NS}_{1/m}(f)\) is \(\Pr [f(X)\neq f(Y)]\) when each coordinate of \(X\) is independently flipped with probability \(1/m\) to obtain \(Y\).

For every \(n\in \mathbb N\), \(f:\{ 0,1\} ^{n}\to \mathbb R\) and real \(\delta \leq \delta '\leq 1/2\), with no lower bound on either rate, one has \(\operatorname {NS}_{\delta }(f)\leq \operatorname {NS}_{\delta '}(f)\), where the total real-valued extension is

For every natural number \(d\), with \(\log \) denoting the natural logarithm,

For every \(n,k\in \mathbb N\) with \(k\leq 1\), if \(f:\{ 0,1\} ^{n}\to \{ -1,1\} \) has a representation \(f(x)=\operatorname {sgn}_{+}(p((-1)^{x_1},\ldots ,(-1)^{x_n}))\) by a real multilinear polynomial \(p\) of degree at most \(k\), then there exist real \(c,a_1,\ldots ,a_n\) such that

where \(\operatorname {sgn}_{+}(t)=1\) for \(t\geq 0\) and \(-1\) for \(t\lt 0\).

For real \(L,E\) and \(d\in \mathbb N\) with \(L\geq \log 2\) and \(0\leq E\leq d\), where \(\log \) is the natural logarithm, one has

with real exponentiation on the positive bases \(L\) and \(\log 2\).

For \(k,d\in \mathbb N\) and real \(E,\delta \) with \(0\leq E\leq d\) and \(0\lt \delta \leq 1/2\), setting \(m=\lfloor 1/\delta \rfloor \) gives

where \(\log \) is the natural logarithm and the powers with real exponents have positive bases.