Noise sensitivity
Probability that f changes when each bit is flipped independently with probability delta.
Definition
$$\mathrm{NS}_\delta(f) = \Pr_{x,\,y\sim N_\delta(x)}[f(x)\ne f(y)] = \tfrac12\Big(1-\sum_S (1-2\delta)^{|S|}\hat f(S)^2\Big).$$ Related to stability by $\mathrm{Stab}_\rho(f) = \sum_S \rho^{|S|}\hat f(S)^2$ with $\rho = 1-2\delta$.
Why this is not a query complexity measure
$\mathrm{NS}_\delta$ is not a query complexity measure, and asking how it compares to $\mathrm{D}$ or $\mathrm{R}$ is a category error. It is a probability, bounded by $1/2$ however hard $f$ is, and it depends on a free parameter $\delta$ that has nothing to do with the size of the input. A row of the matrix for it would be empty for reasons of units, not of ignorance.
The interesting content is in where the transition happens, and that is a number on the query scale. Two normalizations recover it:
- Small $\delta$. As $\delta\to 0$, $\mathrm{NS}_\delta(f)/\delta \to \mathrm{I}(f)$, the total influence -- so the derivative at the origin is already in the zoo as \(\mathrm{I}(f)\), and satisfies $\mathrm{I}(f)\le\mathrm{D}(f)$.
- The critical noise rate. Let $\delta^{*}(f)$ be the smallest $\delta$ at which $\mathrm{NS}_\delta(f)$ reaches a fixed fraction of its maximum. Then $1/\delta^{*}$ is a query count: it is $\Theta(1)$ for a noise-sensitive function like $\mathrm{MAJ}$ and $\Theta(n)$ for a noise-stable one like a dictator or $\oplus_n$. That is the measure \(\mathrm{nsr}(f)\), and it is what appears in the matrix in place of this page.
Note the two point in different directions -- $\mathrm{I}$ is large exactly when $f$ is fragile, $\mathrm{nsr}$ is large exactly when $f$ is robust -- which is why one dimensionless family yields two honest measures rather than one. See Dimensionless quantities and how to normalize them.
Parameters
\(\delta\) (delta) default \(variable\)
per-coordinate flip probability
Basic facts
- $\mathrm{NS}_\delta(f)\le \delta\,\mathrm{I}(f)$.
- $\mathrm{NS}_\delta(f)\ge \delta\,\mathrm{Var}(f)$ for $\delta\le 1/2$: flipping one pivotal coordinate already suffices.
- $\mathrm{NS}_{1/2}(f) = \mathrm{Var}(f)/2$, the maximum, and $\mathrm{NS}_\delta$ is non-decreasing in $\delta$ on $[0,1/2]$.
- $\mathrm{NS}_{1/\mathrm{D}(f)}(f) = O(1)$-type bounds: shallow decision trees are noise-stable, which is the basis of many quantum-vs-classical separations via Fourier growth.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{NS}_{\delta}(f)\). “\(\mathrm{NS}_{\delta}(f)\) in terms of it” is the pair with \(\mathrm{NS}_{\delta}(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 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(2^{1-n}\big(1-(1-\delta)^n\big)\) | Exact, for every $\delta$: $\vee_n(x) \ne \vee_n(y)$ holds precisely when exactly one of $x, y$ is $0^n$, and $\Pr[x = 0^n,\ y \ne 0^n] = 2^{-n}(1-(1-\delta)^n)$. So $\vee_n$ is exponentially noise-stable -- the extreme opposite of \(\oplus_n\). |
| AND total | \(2^{1-n}\big(1-(1-\delta)^n\big)\) | Exact, for every $\delta$: $\wedge_n(x) \ne \wedge_n(y)$ holds precisely when exactly one of $x,y$ equals $1^n$, and $\Pr[x = 1^n,\ y \ne 1^n] = 2^{-n}(1-(1-\delta)^n)$. The mirror of \(\mathrm{OR}_n\) under $x \mapsto \bar x$: exponentially noise-stable. |
| PARITY total | \(\tfrac12\big(1-(1-2\delta)^n\big)\) | Exactly: the noise flips the answer iff an odd number of bits flip. Maximally noise-sensitive. ODonnell14 |
| MAJORITY total | \(\Theta(\sqrt\delta)\) | As $n\to\infty$, $\mathrm{NS}_\delta \to \tfrac1\pi\arccos(1-2\delta)$. Majority is the most noise-stable of all low-influence functions (Majority Is Stablest). ODonnell14 |
| EXACT-HALF total | \(\Theta(1/\sqrt n)\) putative | For every fixed $\delta \in (0,1/2)$. $\mathrm{NS}_\delta = 2\big(M - \Pr[\mathrm{EH}(x)=\mathrm{EH}(y)=1]\big)$ with $M = \binom{n}{n/2}2^{-n} = \Theta(n^{-1/2})$, and the joint probability is $M^2\sum_t \rho^{2t}\binom{n/2}{t}^2/\binom{n}{2t} \to M^2/\sqrt{1-\rho^2}$ at $\rho = 1-2\delta$, of order $1/n$. So $\mathrm{NS}_\delta = 2M(1-o(1))$: noise almost always destroys a $1$, but $1$s are rare, so the function is noise stable in the crude sense while carrying no low-degree structure at all. |
| ODD-MAX-BIT total | \(\tfrac{4\delta}{3(1+\delta)} + o(1)\) putative | For every fixed $\delta$, as $n \to \infty$. Scan positions from the top: at each one the pair $(x_i,y_i)$ is $(0,0)$ with probability $(1-\delta)/2$, so conditioned on the first position $k$ where it is not, the pair is $(1,1)$ with probability $\tfrac{1-\delta}{1+\delta}$ -- both highest ones are then at $k$ and the answers agree -- and is $(1,0)$ or $(0,1)$ with probability $\tfrac{2\delta}{1+\delta}$. In the latter case one highest one is at $k$ and the other is the highest one of a fresh uniform string below $k$, whose position has parity opposite to $k$ with probability $\tfrac12+\tfrac18+\cdots = \tfrac23$. Multiplying gives $\tfrac{2\delta}{1+\delta}\cdot\tfrac23$. So OMB is noise-stable in the sense that $\mathrm{NS}_\delta \to 0$ with $\delta$, uniformly in $n$, unlike \(\oplus_n\) or \(\mathrm{Tribes}_{w,s}\). |
| ADDRESS / multiplexer total | \(\tfrac12\big(1-(1-2\delta)(1-\delta)^{k}\big)\) putative | The \(\mathrm{Stab}_{\rho}(f)\) line at $\rho = 1-2\delta$, through $\mathrm{NS}_\delta = \tfrac12(1-\mathrm{Stab}_{1-2\delta})$. Noise on the address, not on the table, is what destroys the answer: the table contributes only the leading factor $1-2\delta$. |
| Binary tree navigation total | \(\tfrac12\big(1-(1-2\delta)(1-\delta)^{k-1}\big)\) putative | The \(\mathrm{Stab}_{\rho}(f)\) line at $\rho = 1-2\delta$, where $\tfrac{1+\rho}{2} = 1-\delta$, through $\mathrm{NS}_\delta = \tfrac12(1-\mathrm{Stab}_{1-2\delta})$. So navigation becomes noise-sensitive at $\delta = \Theta(1/k)$ -- exponentially earlier in the input length $2^k-1$ than \(\mathrm{MAJ}_n\) does. |
| TRIBES total | \(\tfrac12 - o(1)\) | For any fixed $\delta>0$: TRIBES is the standard example of a noise-sensitive monotone function, because all its influences are $O(\log n/n)$. ODonnell14 |
| AND-OR tree (depth 2) total | \(\Theta(n2^{-n})\) putative | For constant $\delta$ the noise sensitivity is within constants of the variance: in $\mathrm{NS}_\delta = \tfrac12\sum_{S\ne\emptyset}(1-(1-2\delta)^{|S|})\hat f(S)^2$ every factor lies in $[2\delta, 1]$, so $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$. Here $\Pr[f=1] = (1-2^{-n})^n = 1-\Theta(n2^{-n})$, hence $\mathrm{Var} = 4p(1-p) = \Theta(n2^{-n})$. Consistent with the recorded $\mathrm{I}(f) = \Theta(n^2 2^{-n})$ through $\mathrm{NS}_\delta \le \delta\,\mathrm{I}$. ODonnell14 |
| NAND tree (balanced AND-OR formula) total | \(2^{-\Theta(\sqrt N)}\) putative | For constant $\delta$, $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$, since every factor $1-(1-2\delta)^{|S|}$ with $|S|\ge 1$ lies in $[2\delta,1]$. The uniform bias satisfies $p_d = 1-p_{d-1}^2$ from $p_0 = 1/2$, which oscillates and escapes: $p_{2m} \approx 2p_{2m-2}^2$, so $\min\{p_d, 1-p_d\} = 2^{-\Theta(2^{d/2})} = 2^{-\Theta(\sqrt N)}$ and $\mathrm{Var} = 2^{-\Theta(\sqrt N)}$. This is the same doubly exponential collapse that produces the recorded $\mathrm{I}(f) = 2^{-\Theta(\sqrt N)}$. ODonnell14 |
| Recursive MAJORITY-of-3 total | \(\tfrac{1}{2} - \Theta\big((3/4)^{\,d}\big)\) putative | Exactly computable, because $\mathrm{MAJ}_3$ is balanced: $\mathrm{Stab}_\rho(F\circ g^m) = \mathrm{Stab}_{\mathrm{Stab}_\rho(g)}(F)$ when $\mathbb{E}[g]=0$, and $\mathrm{MAJ}_3 = \tfrac12(x_1+x_2+x_3) - \tfrac12 x_1x_2x_3$ in $\pm 1$ gives $\Psi(\rho) := \mathrm{Stab}_\rho(\mathrm{MAJ}_3) = (3\rho+\rho^3)/4$. Since $\Psi(\rho) < \rho$ on $(0,1)$ the iterates fall to $0$, and near $0$ each step multiplies by $\Psi'(0) = 3/4$; hence $\mathrm{Stab}_\rho = \Theta((3/4)^d)$ and $\mathrm{NS}_\delta = (1-\mathrm{Stab}_{1-2\delta})/2 = \tfrac12 - \Theta((3/4)^d)$ for every constant $\delta \in (0,1/2)$. ODonnell14 |
| Kushilevitz's function (iterated) total | \(\tfrac{1}{2} - \Theta\big((3/8)^{\,k}\big)\) putative | The gadget is balanced, so $\mathrm{Stab}_\rho(f\circ g^m) = \mathrm{Stab}_{\mathrm{Stab}_\rho(g)}(f)$ applies. In $\pm 1$ the Kushilevitz gadget is $\tfrac14(\sum_{T\in\mathcal{F}}\chi_T - \sum_i \chi_i)$ with $|\mathcal{F}| = 10$ triples and $6$ singletons (Parseval: $(10+6)/16 = 1$; this also reproduces the recorded $\mathrm{I} = (30+6)/16 = 9/4$ and $\mathrm{MaxInf} = (5+1)/16 = 3/8$). Hence $\Psi_K(\rho) = (3\rho+5\rho^3)/8 < \rho$ on $(0,1)$, with $\Psi_K'(0) = 3/8$, so $\mathrm{Stab} = \Theta((3/8)^k)$ and $\mathrm{NS}_\delta = \tfrac12 - \Theta((3/8)^k)$. ODonnell14 NisanWigderson95 |
| Rubinstein's function total | \(\Theta(n^2 2^{-n})\) putative | For constant $\delta$, $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$, because each factor $1-(1-2\delta)^{|S|}$ with $|S| \ge 1$ lies in $[2\delta,1]$. A block is $1$ on exactly the $n/2$ inputs with one consecutive pair set, so $\Pr[g=1] = (n/2)2^{-n}$ and $\Pr[f=1] = 1-(1-(n/2)2^{-n})^n = \Theta(n^2 2^{-n})$; hence $\mathrm{Var} = 4p(1-p) = \Theta(n^2 2^{-n})$. Consistent with the recorded $\mathrm{I}(f) = \Theta(n^3 2^{-n})$ via $\mathrm{NS}_\delta \le \delta\,\mathrm{I}$. ODonnell14 |
| Ambainis-Sun function total | \(\Theta(k^2 2^{-3k})\) putative | For constant $\delta$, $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$, since every factor $1-(1-2\delta)^{|S|}$ with $|S|\ge 1$ lies in $[2\delta,1]$. The gadget has $\Pr[g=1] = (2k+1)2^{-(3k+2)}$ and $f$ is the $\mathrm{OR}$ of $3k+2$ disjoint copies (the same numbers that give the recorded $\mathrm{I}(f)$), so $\Pr[f=1] = \Theta(k^2 2^{-3k})$ and $\mathrm{Var} = 4p(1-p) = \Theta(k^2 2^{-3k})$. ODonnell14 |
| AND composed with NOT-EXACT-HALF total | \(2^{-\Theta(\sqrt n)}\) putative | For constant $\delta$, $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$, since each factor $1-(1-2\delta)^{|S|}$ with $|S|\ge1$ lies in $[2\delta,1]$. Each of the $n$ blocks is $1$ with probability $1-c$, $c = \Theta(n^{-1/2})$, so $\Pr[f=1] = (1-c)^n = 2^{-\Theta(\sqrt n)}$ and $\mathrm{Var} = 4p(1-p) = 2^{-\Theta(\sqrt n)}$ -- the same collapse that gives the recorded $\mathrm{I}(f) = 2^{-\Theta(\sqrt n)}$. ODonnell14 |
| Gilmer-Saks-Srinivasan functions total | \(2^{-\Theta(n)}\) | For any constant $\delta$: $\mathrm{NS}_\delta\le\delta\,\mathrm{I}(f)=2^{-\Theta(n)}$. |
| Ambainis' exact-quantum function total | \(\Theta(1)\) putative | For every constant $\delta\in(0,1/2)$. Push a $\delta$-correlated pair through the recursion: the joint law of $(\mathrm{NE}^d(x),\mathrm{NE}^d(y))$ is a $3$-fold product-then-gadget map on the four-state joint distribution, with marginal $p_d=\Pr[\mathrm{NE}^d=1]=3p_{d-1}(1-p_{d-1})\to2/3$. Iterating it numerically, the orbit is independent of $\delta$ (tested at $\delta$ corresponding to $\rho\in\{0.01,0.5,0.99\}$) from about $d=10$ on, and $\mathrm{NS}_\delta$ climbs to $4/9$ from below: $0.468$ at $d=30$, $0.452$ at $d=400$. So a constant flip rate destroys all correlation except what the bias forces. |
| Surjectivity total | \(2^{-\Theta(n/\log n)}\) | Sandwiched by the two recorded influence values: $\delta\,\mathrm{MaxInf}\le\mathrm{NS}_\delta\le\delta\,\mathrm{Inf}$, and both $\mathrm{Inf}$ and $\mathrm{MaxInf}$ are $2^{-\Theta(n/\log n)}$ here. A random list of $N$ elements of $[R]$ is almost never surjective, and it takes a coordinated flip to change that. |
| Triangle finding total | \(2^{-\Theta(m^2)}\) | $\delta\,\mathrm{MaxInf}\le\mathrm{NS}_\delta\le\delta\,\mathrm{Inf}$, and both recorded influence values are $2^{-\Theta(m^2)}$: a uniformly random graph contains a triangle with overwhelming probability, so resampling a $\delta$-fraction of the edges almost never changes the answer. |
| Inner product mod 2 total | \(\tfrac12\big(1 - (1-\delta)^{n}\big)\) | Substituting $\rho = 1-2\delta$ into $\mathrm{Stab}$ above. So $\mathrm{NS}_\delta \to 1/2$ once $\delta \gg 1/n$ -- IP is as noise-sensitive as a random function. |
| Minsky-Papert one-in-a-box total | \((2+o(1))\,m\,2^{-m^2}\big(1-(1-\delta)^{m^2}\big)\) putative | Almost every input is a $1$-input; noise flips the answer essentially only by emptying the one box that was a singleton away from empty. Exactly, $\mathrm{NS}_\delta = \tfrac12(1-\mathrm{Stab}_{1-2\delta})$ with the $\mathrm{Stab}$ below. Consistency check: as $\delta \to 0$ this is $\delta\cdot 2m^3 2^{-m^2} = (1+o(1))\,\delta\,\mathrm{I}(f)$, matching $\mathrm{NS}_\delta \approx \delta\,\mathrm{I}$. |
| Sink of a tournament total | \((1+o(1))\,m\,2^{2-m}\big(1-(1-\delta)^{m-1}\big)\) putative | A random tournament has a sink with probability $m2^{1-m}$, and the sink survives $\delta$-noise exactly when none of its $m-1$ in-edges flips; a new sink appearing needs $\ge m-2$ simultaneous flips and is lower order. So $\mathrm{NS}_\delta = 2\Pr[f(x)=1]\big(1-(1-\delta)^{m-1}\big)(1+o(1))$. Consistency check: as $\delta \to 0$ this is $\delta\,m(m-1)2^{2-m} = \delta\,\mathrm{I}(f)$ exactly. |
| Scorpion graphs total | \((2+o(1))\,m(m-1)(m-2)\,2^{6-3m}\big(1-(1-\delta)^{3m-6}\big)\) putative | Noise sensitivity is $2\Pr[f(x)=1,\,f(y)=0]$. A uniform graph is a scorpion with probability $p = m(m-1)(m-2)2^{6-3m}$, and given a scorpion with triple $(s,t,b)$ the noisy copy stays a scorpion essentially only if none of the $3m-6$ touch pairs flips -- acquiring a different triple needs $\Omega(m)$ flips and costs a further $2^{-\Omega(m)}$ -- whence the displayed formula. Consistency: as $\delta \to 0$ it tends to $6m(m-1)(m-2)^2 2^{6-3m}\,\delta = \delta\,\mathrm{I}(f)$, exactly the recorded \(\mathrm{I}(f)\). |
| Graph connectivity total | \((1+o(1))\,m\,2^{2-m}\big(1-(1-\delta)^{m-1}\big)\) putative | Noise sensitivity is $2\Pr[f(x)=1,f(y)=0] = 2(\Pr[\text{disconnected}] - \Pr[\text{both disconnected}])$. Disconnection is dominated by a single isolated vertex, of probability $m2^{1-m}$, and a vertex is isolated in both $x$ and its $\delta$-noisy copy with probability $((1-\delta)/2)^{m-1}$ per vertex, whence the formula. Consistency: as $\delta \to 0$ it tends to $m(m-1)2^{2-m}\delta = \delta\,\mathrm{I}(f)$, exactly the recorded \(\mathrm{I}(f)\). Exact computation gives ratios $0.60,\,0.74,\,0.86,\,0.93$ to the formula at $m = 4,5,6,7$ with $\delta = 0.05$ -- the same slow $1+o(1)$ convergence as \(\mathrm{I}(f)\) itself. |