Q The Query Complexity Zoo
\(\mathrm{Stab}_{\rho}(f)\)

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.

Other measure \(\mathrm{Stab}_{\rho}(f)\) in terms of it It in terms of \(\mathrm{Stab}_{\rho}(f)\)
\(\mathrm{nsr}(f)\) Noise robustness —derived open pair → total∞ derived open pair →
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity total∞ open pair → total∞ open pair →
\(\mathrm{Var}(f)\) Variance —derived open pair → —derived open pair →
\(\mathrm{I}(f)\) Total influence (L2 influence) —derived open pair → total∞ open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
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)$.