Q The Query Complexity Zoo
\(\mathrm{nsr}(f)\)

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.

Other measure \(\mathrm{nsr}(f)\) in terms of it It in terms of \(\mathrm{nsr}(f)\)
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity total∞ derived open pair → —derived open pair →
\(\mathrm{Stab}_{\rho}(f)\) Noise stability total∞ derived open pair → —derived open pair →
\(\mathrm{Var}(f)\) Variance total∞ derived open pair → —derived open pair →
\(\mathrm{osss}(f)\) OSSS number total∞ derived open pair → total∞ derived open pair →
\(\mathrm{I}(f)\) Total influence (L2 influence) total2,? derived open pair → total∞ derived open pair →
\(\mathrm{s}(f)\) Sensitivity total1,1 open pair → total∞ derived open pair →

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

Known values

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