Noise robustness
One over the noise rate at which f starts to break: the query-scale reading of NS_delta.
also written:
1/delta*, critical noise rate (inverse), noise length, \(1/\delta^{*}(f)\)
Definition
Let $$\delta^{*}(f) \;=\; \min\{\delta : \mathrm{NS}_\delta(f)\ \ge\ \mathrm{Var}(f)/4\}, \qquad \mathrm{nsr}(f) \;=\; 1/\delta^{*}(f).$$ In words: flip each bit independently with probability $\delta$ and increase $\delta$ until $f$ has lost half the agreement it can possibly lose ($\mathrm{NS}_{1/2} = \mathrm{Var}/2$ is the maximum, so $\mathrm{Var}/4$ is the halfway point). $\mathrm{nsr}(f)$ is then roughly how many coordinates of noise the function tolerates: $\oplus_n$ only breaks once $\delta\sim 1/n$, giving $\mathrm{nsr} = \Theta(n)$, while $\mathrm{MAJ}_n$ is already half broken at constant $\delta$, giving $\mathrm{nsr} = \Theta(1)$.
The $\mathrm{Var}/4$ threshold is this zoo's convention, not a standard one. Any fixed fraction of the maximum gives the same measure up to a constant factor: $\mathrm{NS}_\delta$ is non-decreasing in $\delta$, and noise at rate $k\delta$ is dominated by $k$ independent rounds at rate $\delta$, so $\mathrm{NS}_{k\delta}\le k\,\mathrm{NS}_\delta$ for integer $k$ and the threshold cannot move by more than a constant. Constants are therefore not meaningful here and every value is recorded up to $\Theta(\cdot)$. See Dimensionless quantities and how to normalize them for why the dimensionless \(\mathrm{NS}_{\delta}(f)\) is presented this way.
Basic facts
- $\mathrm{nsr}(f)\ge 4$ always, since $\mathrm{NS}_\delta\ge\delta\,\mathrm{Var}$ forces $\delta^{*}\le 1/4$. Constants aside: $\mathrm{nsr}\ge 1$.
- $\mathrm{nsr}(f)\le 4\,\mathrm{I}(f)/\mathrm{Var}(f)$, from $\mathrm{NS}_\delta\le\delta\,\mathrm{I}$.
- $\mathrm{nsr}(f) = O(\mathrm{s}(f))$, hence $O(\mathrm{D}(f))$: for a balanced-or-lighter $f$ the edge count gives $\mathrm{I}(f)\le \mathrm{s}(f)\,\mathrm{Var}(f)$, and combining with the line above kills the $\mathrm{Var}$.
- Incomparable to \(\mathrm{osss}(f)\), the other normalization of a dimensionless Fourier quantity: $\oplus_n$ has $\mathrm{osss} = 1$ but $\mathrm{nsr} = \Theta(n)$, and $\mathrm{MAJ}_n$ has $\mathrm{osss} = \Theta(\sqrt n)$ but $\mathrm{nsr} = \Theta(1)$.
- Large $\mathrm{nsr}$ means robust, so it behaves oppositely to \(\mathrm{I}(f)\) on the same data: the two are the $\delta\to 0$ and $\delta\to\delta^{*}$ readings of the same curve.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{nsr}(f)\). “\(\mathrm{nsr}(f)\) in terms of it” is the pair with \(\mathrm{nsr}(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 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(n)\) putative | $\mathrm{NS}_\delta = 2^{1-n}(1-(1-\delta)^n)$ crosses $\mathrm{Var}/4 = 2^{-n}(1-2^{-n})$ at $(1-\delta)^n = \tfrac12(1+2^{-n})$, i.e. $\delta^{*} = (\ln 2)/n\,(1+o(1))$. Tight against $\mathrm{nsr} \le 4\mathrm{s} = 4n$: an OR tolerates as much noise as anything on $n$ relevant variables can. |
| AND total | \(\Theta(n)\) putative | Identical to \(\mathrm{OR}_n\) by De Morgan; $\delta^{*} = (\ln 2)/n\,(1+o(1))$. |
| PARITY total | \(2n/\ln 2\,(1+o(1)) = \Theta(n)\) putative | $\tfrac12(1-(1-2\delta)^n) = \tfrac14$ at $(1-2\delta)^n = \tfrac12$, so $\delta^{*} = (\ln 2)/(2n)(1+o(1))$. Maximally noise-robust at the scale that matters, which is the opposite reading of the same function from $\mathrm{NS}_{1/2} = \tfrac12$. |
| MAJORITY total | \(4+2\sqrt2 + o(1) = \Theta(1)\) putative | In the $n\to\infty$ limit $\mathrm{NS}_\delta = \tfrac1\pi\arccos(1-2\delta)$, which reaches $\mathrm{Var}/4 = \tfrac14$ at $1-2\delta = \cos(\pi/4)$, i.e. $\delta^{*} = \tfrac12(1-1/\sqrt2) \approx 0.1464$. Majority is noise-sensitive at constant rate even though it is the most stable low-influence function -- the two statements live at different scales. |
| EXACT-HALF total | \(\Theta(n)\) putative | At $\delta = c/n$ the number of flipped bits is $\mathrm{Poisson}(c)$-like, and a $1$-input survives only if the flips are exactly balanced between the two halves, which fails with probability bounded away from $0$ and $1$. So $\delta^{*} = \Theta(1/n)$ and the value is tight against $\mathrm{nsr} = O(\mathrm{s}) = O(n)$ and against $\mathrm{D} = n$. |
| ODD-MAX-BIT total | \(5 + o(1)\) putative | Solving $\mathrm{NS}_\delta = \tfrac{4\delta}{3(1+\delta)} = \mathrm{Var}/4 = 2/9$ gives $\delta^{*} = 1/5$ exactly, in the $n\to\infty$ limit. One of the few functions here whose critical noise rate is a constant that can be written down. |
| ADDRESS / multiplexer total | \(k/\ln 2\,(1+o(1)) = \Theta(\log N)\) putative | $\tfrac12(1-(1-2\delta)(1-\delta)^k) = \tfrac14$ at $(1-\delta)^k \to \tfrac12$, so $\delta^{*} = (\ln 2)/k\,(1+o(1))$: the answer survives exactly as long as none of the $k$ address bits flips. Tight against $\mathrm{D} = k+1$ -- one of the few functions in the zoo where the critical noise rate sees the whole decision tree. |
| Binary tree navigation total | \(k/\ln 2\,(1+o(1)) = \Theta(k)\) putative | $(1-2\delta)(1-\delta)^{k-1} = \tfrac12$ gives $\delta^{*} = (\ln 2)/k\,(1+o(1))$: the walk survives until one of the $k$ navigation bits flips. Tight against $\mathrm{D} = k$. |
| TRIBES total | \(\Theta(\log n)\) putative | Upper: $\mathrm{nsr}\le 4\mathrm{I}/\mathrm{Var} = \Theta(\log n)$. Lower: a uniform input has $\Theta(\log n)$ tribes that are a single $0$ away from firing, so at $\delta = c/\log n$ one of them flips with constant probability and $\mathrm{NS}_\delta = \Omega(1)$. Note $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(n)$, as for every transitive function whose $\mathrm{NS}_\delta \le \delta\mathrm{I}$ bound is tight. |
| AND-OR tree (depth 2) total | \(\Theta(n) = \Theta(\sqrt N)\) putative | $\mathrm{NS}_\delta = 2\Pr[f(x)=1,f(y)=0] = (2+o(1))n2^{-n}(1-(1-\delta)^n)$: the answer is $0$ only when some block is all-zero, and such a block stays all-zero exactly when none of its $n$ bits flips. Crossing $\mathrm{Var}/4$ needs $(1-\delta)^n \le \tfrac12$, so $\delta^{*} = \Theta(1/n)$. Tight against $4\mathrm{s} = 4n$. |
| NAND tree (balanced AND-OR formula) total | \(O(\sqrt N)\) putative | $\mathrm{nsr}\le 4\mathrm{I}/\mathrm{Var} = 4N/\mathrm{osss} = \Theta(\sqrt N)$ by the \(\mathrm{osss}(f)\) entry. A first-moment count suggests this is tight -- conditioned on the rare event $f = 1$, an input has $\Theta(\sqrt N)$ sensitive coordinates on average, so noise at rate $\Theta(1/\sqrt N)$ should already flip the answer -- but the matching lower bound is not recorded here. |
| Recursive MAJORITY-of-3 total | \(\Theta((3/2)^d) = \Theta(N^{0.3691})\) putative | Near $\rho = 1$ the stability recursion $\Psi(\rho) = (3\rho+\rho^3)/4$ of the \(\mathrm{NS}_{\delta}(f)\) entry acts as $1-\varepsilon \mapsto 1-\tfrac32\varepsilon$, so starting from $\varepsilon = 2\delta$ the stability leaves the neighbourhood of $1$ after $(3/2)^d\delta = \Theta(1)$, i.e. $\delta^{*} = \Theta((2/3)^d)$. Equal to $\mathrm{I}(f) = (3/2)^d$, so the bound $\mathrm{nsr}\le 4\mathrm{I}/\mathrm{Var}$ is tight and $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(N)$. |
| Kushilevitz's function (iterated) total | \(\Theta((9/4)^k) = \Theta(N^{0.4526})\) putative | The stability recursion $\Psi_K(\rho) = (3\rho+5\rho^3)/8$ of the \(\mathrm{NS}_{\delta}(f)\) entry acts as $1-\varepsilon\mapsto 1-\tfrac94\varepsilon$ near $\rho = 1$, so $\delta^{*} = \Theta((4/9)^k)$. Equal to $\mathrm{I}(f)$, so $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(N)$ as for every transitive function whose $\mathrm{NS}_\delta\le\delta\mathrm{I}$ bound is tight. |
| Rubinstein's function total | \(\Theta(n) = \Theta(\sqrt N)\) putative | A firing gadget pins all $n$ of its bits, so it survives $\delta$-noise with probability $(1-\delta)^n$ and $\mathrm{NS}_\delta = (2+o(1))p(1-(1-\delta)^n)$ against $\mathrm{Var}/4 = (1+o(1))p$. Hence $\delta^{*} = \Theta(1/n)$, tight against $4\mathrm{s} = 4n$. |
| Ambainis-Sun function total | \(\Theta(k) = \Theta(\sqrt N)\) putative | A firing pattern pins $3k+2$ coordinates, so $\mathrm{NS}_\delta = (2+o(1))p(1-(1-\delta)^{3k+2})$ crosses $\mathrm{Var}/4$ at $\delta^{*} = \Theta(1/k)$. Tight against $4\mathrm{s} = 4(3k+2)$. |
| Inner product mod 2 total | \(n/\ln 2\,(1+o(1)) = \Theta(n)\) putative | $\tfrac12(1-(1-\delta)^n) = \mathrm{Var}/4$ at $(1-\delta)^n \to \tfrac12$. Tight against $\mathrm{s} = \mathrm{D} = n$, and the exact complement of the \(\mathrm{osss}(f)\) reading: the same flat spectrum that makes OSSS useless makes the critical noise rate optimal. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^2) = \Theta(N^{2/3})\) putative | $\mathrm{NS}_\delta = (2+o(1))m2^{-m^2}(1-(1-\delta)^{m^2})$ crosses $\mathrm{Var}/4$ at $(1-\delta)^{m^2} = \tfrac12$, so $\delta^{*} = \Theta(1/m^2)$: the answer changes when the one nearly-empty box loses its last element. Tight against $\mathrm{s} = m^2$, and $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(N)$ -- the two normalizations split the $\mathrm{AND}\circ\mathrm{OR}$ tree between its two levels. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) putative | The sink survives $\delta$-noise exactly when none of its $m-1$ in-edges flips, so $\mathrm{NS}_\delta$ crosses $\mathrm{Var}/4$ at $(1-\delta)^{m-1} = \tfrac12$ and $\delta^{*} = \Theta(1/m)$. Also tight against $\mathrm{D} = \Theta(m)$. |
| Scorpion graphs total | \(\Theta(m)\) putative | A scorpion is destroyed when one of the $3m-6$ pinned adjacencies flips, so $\mathrm{NS}_\delta$ crosses $\mathrm{Var}/4$ at $(1-\delta)^{3m-6} = \tfrac12$ and $\delta^{*} = \Theta(1/m)$. Tight: equal to $\mathrm{s} = 3m-6$ up to constants, so this is the witness for \(\mathrm{nsr}(f)\) vs \(\mathrm{s}(f)\), and equal to $\mathrm{D} = \Theta(m)$ as well. |
| Graph connectivity total | \(\Theta(m) = \Theta(\sqrt N)\) putative | An isolated vertex stays isolated unless one of its $m-1$ non-edges flips, so $\delta^{*} = \Theta(1/m)$. Quadratically short of $4\mathrm{s} = \Theta(N)$, so CONN is where the $\mathrm{nsr} = O(\mathrm{s})$ bound is loosest. |