Noise stability
Correlation of f(x) and f(y) for rho-correlated x,y.
Definition
$\mathrm{Stab}_\rho(f)=\mathbb{E}[f(x)f(y)]=\sum_S\rho^{|S|}\hat f(S)^2$ for $\rho$-correlated $x,y$.
Why this is not a query complexity measure
Stability and sensitivity are the same information written twice: $\mathrm{Stab}_{1-2\delta}(f) = 1-2\,\mathrm{NS}_\delta(f)$, and in particular $\mathrm{Stab}_0(f) = 1-\mathrm{Var}(f)$. So everything said on the \(\mathrm{NS}_{\delta}(f)\) page applies here: this is a correlation, not a cost, and it is normalized onto the query scale in the same two ways -- the derivative at $\rho=1$, which is $\mathrm{I}(f)$ (see \(\mathrm{I}(f)\)), and the correlation length $1/\delta^{*}$, which is the measure \(\mathrm{nsr}(f)\) that appears in the matrix. See Dimensionless quantities and how to normalize them.
Parameters
\(\rho\) (rho) default \(variable\)
Basic facts
- $\mathrm{Stab}_\rho(f) = 1-2\,\mathrm{NS}_{(1-\rho)/2}(f)$; in particular $\mathrm{Stab}_0(f) = 1-\mathrm{Var}(f) = \hat f(\emptyset)^2$.
- $\tfrac{d}{d\rho}\mathrm{Stab}_\rho(f)\big|_{\rho=1} = \mathrm{I}(f)$.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Stab}_{\rho}(f)\). “\(\mathrm{Stab}_{\rho}(f)\) in terms of it” is the pair with \(\mathrm{Stab}_{\rho}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(1 - 2^{2-n}\big(1-(\tfrac{1+\rho}{2})^n\big)\) | From $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the entry above. Tends to $1$ for every fixed $\rho$. |
| AND total | \(1 - 2^{2-n}\big(1-(\tfrac{1+\rho}{2})^n\big)\) | From $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the entry above. Tends to $1$ for every fixed $\rho$. |
| PARITY total | \(\rho^{\,n}\) | ODonnell14 |
| MAJORITY total | \(\tfrac{2}{\pi}\arcsin\rho + o(1)\) | Sheppard formula, in the $n\to\infty$ limit. ODonnell14 |
| EXACT-HALF total | \(1 - \Theta(1/\sqrt n)\) putative | The \(\mathrm{NS}_{\delta}(f)\) line through $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$, for every fixed $\rho \in (-1,1)$. The exponentially unbalanced $\pm1$ encoding is what makes this tend to $1$; the whole spectrum above level $0$ carries weight only $4M(1-M) = \Theta(n^{-1/2})$. |
| ODD-MAX-BIT total | \(1 - \tfrac{8(1-\rho)}{3(3-\rho)} + o(1)\) putative | From $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) line. It is $1/9$ at $\rho = 0$, so two independent uniform inputs still give correlated answers -- the highest-one statistic is dominated by the top few coordinates. |
| ADDRESS / multiplexer total | \(\rho\big(\tfrac{1+\rho}{2}\big)^{k}\) putative | Exactly. In the $\pm1$ basis $g = 2^{-k}\sum_a\sum_{S \subseteq [k]} \pm\,\chi_S\,Y_a$, so every one of the $4^k$ Fourier coefficients is $\pm2^{-k}$ and the set $S \cup \{y_a\}$ has size $|S|+1$; summing, $\mathrm{Stab}_\rho = 2^{-2k}\,2^k\rho\sum_{S}\rho^{|S|} = 2^{-k}\rho(1+\rho)^k$. Identical in form to \(\mathrm{Nav}_k\) with one more level, as it should be. |
| Binary tree navigation total | \(\rho\big(\tfrac{1+\rho}{2}\big)^{k-1}\) putative | From the $\pm1$ recursion $\mathrm{Nav}_k = \tfrac{L+R}{2} + x_0\tfrac{L-R}{2}$ on disjoint variable sets: the four monomial groups are disjoint, so $\mathrm{Stab}_\rho(k) = \tfrac{1+\rho}{2}\,\mathrm{Stab}_\rho(k-1)$ with $\mathrm{Stab}_\rho(1) = \rho$. Checked at $k=2$ against the multiplexer spectrum $\{\pm\tfrac12\}$ on four sets. |
| TRIBES total | \(o(1)\) | For every fixed $\rho \in (-1,1)$, from $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and $\mathrm{NS}_\delta \to 1/2$. TRIBES is balanced and noise sensitive, so correlation between $f(x)$ and $f(y)$ vanishes -- the extreme opposite of \(\mathrm{MAJ}_n\). ODonnell14 |
| AND-OR tree (depth 2) total | \(1 - \Theta(n2^{-n})\) putative | From $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. The function is overwhelmingly biased towards $1$, so it is almost perfectly noise stable at every constant $\rho$ -- which is why the OSSS bound $\mathrm{D} \ge \mathrm{Var}/\mathrm{MaxInf}$ gives only $\Theta(n)$ here and not $\Theta(N)$. |
| NAND tree (balanced AND-OR formula) total | \(1 - 2^{-\Theta(\sqrt N)}\) putative | From $\mathrm{Stab}_\rho = 1-2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: at any constant noise rate the tree is essentially constant, so it is almost perfectly stable. |
| Recursive MAJORITY-of-3 total | \(\Theta\big((3/4)^{\,d}\big) = \Theta(N^{-0.2619})\) putative | The iteration $\rho \mapsto (3\rho+\rho^3)/4$ of the \(\mathrm{NS}_{\delta}(f)\) entry, run $d$ times from any constant $\rho \in (0,1)$, converges to $0$ at rate $3/4$ per level: $\mathrm{Stab}_\rho(f) = \Theta((3/4)^d) = \Theta(N^{\log_3(3/4)}) = \Theta(N^{-0.2619})$. Recursive majority is thus noise sensitive -- a random-looking balanced function -- even though it is a read-once formula. ODonnell14 |
| Kushilevitz's function (iterated) total | \(\Theta\big((3/8)^{\,k}\big) = \Theta(N^{-0.5474})\) putative | Iterating $\Psi_K(\rho) = (3\rho+5\rho^3)/8$ from the \(\mathrm{NS}_{\delta}(f)\) entry $k$ times drives any constant $\rho$ to $0$ at rate $3/8$ per level, so $\mathrm{Stab}_\rho = \Theta((3/8)^k) = \Theta(N^{\log_6(3/8)}) = \Theta(N^{-0.5474})$. Strongly noise sensitive, as the fully block-sensitive $\mathrm{bs} = N$ suggests. ODonnell14 |
| Rubinstein's function total | \(1 - \Theta(n^2 2^{-n})\) putative | From $\mathrm{Stab}_\rho = 1-2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: the function is almost always $0$, hence almost perfectly noise stable. |
| Ambainis-Sun function total | \(1 - \Theta(k^2 2^{-3k})\) putative | From $\mathrm{Stab}_\rho = 1-2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: almost always $0$, hence almost perfectly noise stable. |
| AND composed with NOT-EXACT-HALF total | \(1 - 2^{-\Theta(\sqrt n)}\) putative | From $\mathrm{Stab}_\rho = 1-2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: the $\mathrm{AND}$ is almost always $0$, hence almost perfectly noise stable. |
| Gilmer-Saks-Srinivasan functions total | \(1-2^{-\Theta(n)}\) | For any constant $\rho$: $f$ takes the value $1$ with probability $n\,2^{-49n/50}$, so $\Pr[f(x)\ne f(y)]\le 2\Pr[f=1]=2^{-\Theta(n)}$ for correlated $x,y$, giving $\mathrm{Stab}_\rho=1-2^{-\Theta(n)}$ -- the function is essentially constant in the Fourier-analytic sense despite being maximally hard to query. |
| Ambainis' exact-quantum function total | \(\Theta(1)\) putative | Same recursion as \(\mathrm{NS}_{\delta}(f)\): for every constant $\rho\in(0,1)$, $\mathrm{Stab}_\rho\to 1/9$, and numerically $\mathrm{Stab}_\rho$ agrees with $\hat f(\emptyset)^2=(1-2p_d)^2$ to six decimals by $d=30$ for $\rho$ anywhere in $[0.01,0.99]$. That is, $\mathrm{Stab}_\rho-\hat f(\emptyset)^2\to0$: all Fourier weight above level $0$ is noise-sensitive in the Benjamini-Kalai-Schramm sense, consistent with $\mathrm{MaxInf}=(5/9)^{d+o(d)}\to0$. $\mathrm{Stab}$ itself stays $\Theta(1)$ only because the function is biased. Note the contrast with $\mathrm{RS}=\mathrm{R}=3^d$: query complexity maximal, stability constant, exactly the incomparability that \(\mathrm{MAJ}_n\) witnesses. |
| Surjectivity total | \(1 - 2^{-\Theta(n/\log n)}\) | $\mathrm{Stab}_\rho=1-2\,\mathrm{NS}_\delta$ at $\rho=1-2\delta$ in the $\pm1$ normalisation, and $\mathrm{NS}_\delta=2^{-\Theta(n/\log n)}$. Surjectivity is a near-constant function on the uniform measure, so it is as stable as a constant to within its tiny bias. |
| Triangle finding total | \(1 - 2^{-\Theta(m^2)}\) | $\mathrm{Stab}_\rho=1-2\,\mathrm{NS}_\delta$ at $\rho=1-2\delta$, and $\mathrm{NS}_\delta=2^{-\Theta(m^2)}$. Triangle-freeness is a vanishingly rare event, so the function is nearly constant and nearly perfectly stable. |
| Inner product mod 2 total | \(\big(\tfrac{1+\rho}{2}\big)^{n}\) | $\mathrm{Stab}_\rho = \sum_S \rho^{|S|}\hat f(S)^2 = 2^{-n}\sum_S \rho^{|S|} = 2^{-n}(1+\rho)^n$. Exponentially unstable: at any fixed $\rho < 1$ the correlation dies at a constant rate per bit. |
| Minsky-Papert one-in-a-box total | \(1 - (4+o(1))\,m\,2^{-m^2}\big(1-(\tfrac{1+\rho}{2})^{m^2}\big)\) putative | Exactly $1 - 4\mu + 4\nu^{m}$ with $\mu = (1-2^{-m^2})^{m}$ and $\nu = 1 - 2^{1-m^2} + (\tfrac{1+\rho}{4})^{m^2}$, since the boxes are independent and a $\rho$-correlated pair keeps a given box empty with probability $(\tfrac{1+\rho}{4})^{m^2}$. Checks: $\rho = 1$ gives $1$, and $\rho = 0$ gives $(1-2\mu)^2 = \mathbb{E}[F]^2$. Unlike \(\mathrm{IP}_n\), MP is almost perfectly noise-stable, because it is almost constant. |
| Sink of a tournament total | \(1 - m2^{3-m}\big(1-(\tfrac{1+\rho}{2})^{m-1}\big)\) putative | Substituting $\delta = (1-\rho)/2$ into $\mathrm{NS}$ above, via $\mathrm{Stab}_\rho = 1 - 2\mathrm{NS}_\delta$. SINK is almost perfectly noise-stable simply because it is almost always $0$. |
| Scorpion graphs total | \(1 - (4+o(1))\,m(m-1)(m-2)\,2^{6-3m}\big(1-(\tfrac{1+\rho}{2})^{3m-6}\big)\) putative | From $\mathrm{Stab}_{\rho} = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. Stability is $1 - 2^{-\Theta(m)}$ for every fixed $\rho < 1$: the $\pm1$ version of the scorpion property is a constant function up to an exponentially small correction, which is the Fourier shadow of $\mathrm{I}(f) = 2^{-\Theta(\sqrt N)}$. |
| Graph connectivity total | \(1 - (1+o(1))\,m\,2^{3-m}\big(1-(\tfrac{1+\rho}{2})^{m-1}\big)\) putative | From $\mathrm{Stab}_{\rho} = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. For every fixed $\rho < 1$ stability is $1 - \Theta(m2^{-m})$: almost all the Fourier mass of the $\pm1$ version sits on the empty set, which is why $\mathrm{I}(f) = o(1)$ while $\mathrm{s} = \Theta(N)$. |