Q The Query Complexity Zoo
\(\mathrm{N}_{p}(f)\)

Noisy decision tree complexity

Number of queries when every query answer is independently flipped with probability p.

also written: noisy query complexity (FRPU model), noisy oracle complexity

Definition

In the model of Feige-Raghavan-Peleg-Upfal each query (repeats allowed) returns $x_i \oplus \eta$ where $\eta = 1$ with probability $p \in (0,1/2)$ independently each time. $\mathrm{N}_p(f)$ is the least number of queries needed to output $f(x)$ with error $\le 1/3$.

This is a different notion from \(\mathrm{noisyR}(f)\): here the noise rate is imposed by the model, and repetition is the only way to reduce it, whereas in the Ben-David-Blais model the algorithm chooses the bias and pays for it.

Parameters

\(p\) (p) default \(constant in (0,1/2)\)

per-query flip probability

For constant $p$, changing $p$ changes $\mathrm{N}_p$ by only a constant factor (each "reliable" bit costs $\Theta(\log(1/\delta)/(1-2p)^2)$ repetitions). The interesting dependence is on the target error and on $n$.

Detailed records: \(\mathrm{N}_{p}(f) \text{ as a function of the flip probability } p\)

Basic facts

  • $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ always (amplify each query by $O(\log \mathrm{R})$ repetitions and union bound).
  • $\mathrm{N}_p(\mathrm{PARITY}_n) = \Theta(n\log n)$ [FRPU94] -- the log factor is necessary, giving a genuine separation from $\mathrm{R}$.
  • Average-case/Fourier lower bound: $\mathrm{N}_p(f) = \Omega\!\big(\sum_S |\hat f(S)|^2 |S| \log|S|\big)$-flavoured bounds [Evans-Pippenger].
  • $\mathrm{N}_p(f) = \Omega(\mathrm{I}(f)\log \mathrm{I}(f))$ for every total $f$ [GLX26noisy] -- the first general lower bound beyond the trivial $\mathrm{N}_p(f) = \Omega(\mathrm{R}(f))$, and tight at PARITY.
  • Almost all $f$ need $\Omega(n\log n)$ noisy queries [Reischuk-Schmeltz].
  • Quantum contrast: the robust quantum query complexity of PARITY is $\Theta(n)$ -- no log factor [BNRdW05].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{N}_{p}(f)\). “\(\mathrm{N}_{p}(f)\) in terms of it” is the pair with \(\mathrm{N}_{p}(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{N}_{p}(f)\) in terms of it It in terms of \(\mathrm{N}_{p}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity total1.1,3 partialexp,? relation∞ derived open pair → total1,1 partial1,1 relation1,1 derived open pair →
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity total3,4 partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 derived open pair →
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity total∞ open pair → —derived 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 \(\Theta(n)\)· Constant-rate noise costs only a constant factor here, unlike PARITY. FRPU94
AND total \(\Theta(n)\)· Noisy decision trees are unaffected by negating input bits or complementing the output, and $\wedge_n(x) = \lnot\vee_n(\bar x)$, so this is the \(\mathrm{OR}_n\) value: constant-rate noise costs only a constant factor, unlike \(\oplus_n\). FRPU94
PARITY total \(\Theta(n\log n)\) The canonical example where constant-rate noise costs a $\log n$ factor; matching upper bound in [FRPU94], matching lower bound in [EvansPippenger98]. FRPU94 EvansPippenger98
MAJORITY total \(\Theta(n\log n)\)· putative Upper: $O(\mathrm{R}\log \mathrm{R})$ by repeating each query $O(\log n)$ times. Lower: on inputs of weight $(n\pm1)/2$ the answer is determined by a margin of one bit, so an estimator of the weight must have error variance $o(1)$; a coordinate read $k$ times still has posterior error probability $2^{-\Theta(k)}$, contributing $\Theta(n2^{-\Theta(k)})$ to the variance of the estimated weight, which forces $k = \Omega(\log n)$ on a constant fraction of the coordinates. So noisy majority is a second natural $\Theta(n\log n)$ family alongside \(\oplus_n\) -- and the $\Omega(\mathrm{I}\log\mathrm{I})$ bound of [GLX26noisy] only gives $\Omega(\sqrt n\log n)$ here, so it is not the binding constraint. FRPU94
Threshold total \(\Omega(n),\ O(n\log n)\)· Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$, uniformly in $k$. Upper: $O(\mathrm{R}\log\mathrm{R})$ by repeating each query $O(\log n)$ times. Recorded as a range because the truth genuinely depends on $k$: the log factor is needed at $k = (n+1)/2$ (\(\mathrm{MAJ}_n\), $\Theta(n\log n)$) and is not needed at $k = 1$ (\(\mathrm{OR}_n\), $\Theta(n)$). The influence-based bound $\mathrm{N}_p = \Omega(\mathrm{I}\log\mathrm{I})$ [GLX26noisy] with $\mathrm{I} = n\binom{n-1}{k-1}2^{1-n}$ interpolates between the two. FRPU94 GLX26noisy
Symmetric functions (general) total \(\Omega(n),\ O(n\log n)\)· Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$. Upper: $O(\mathrm{R}\log\mathrm{R})$ by repeating each query. Recorded as a range because both ends occur inside the family and are not a function of $\Gamma$ alone: \(\mathrm{OR}_n\) sits at $\Theta(n)$ [FRPU94] while \(\oplus_n\), \(\mathrm{MAJ}_n\) and \(\mathrm{EH}_n\) all need $\Theta(n\log n)$. The general bound $\mathrm{N}_p = \Omega(\mathrm{I}\log\mathrm{I})$ [GLX26noisy] together with the \(\mathrm{I}(f)\) line decides many individual cases. FRPU94 GLX26noisy
EXACT-HALF total \(\Theta(n\log n)\)· putative Upper: $O(\mathrm{R}\log \mathrm{R})$ by repeating each query. Lower: as for \(\mathrm{MAJ}_n\), only more so -- the answer changes when a single bit moves the weight off $n/2$, so every coordinate must be resolved to error $o(1/n)$, costing $\Omega(\log n)$ repetitions each. FRPU94
ODD-MAX-BIT total \(\Omega(n),\ O(n\log n)\) Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$. Upper: repeat each query $O(\log n)$ times. The influence-based lower bound of the \(\mathrm{N}_{p}(f)\) record gives nothing here, since $\mathrm{I}(\mathrm{OMB}) = \Theta(1)$ -- so unlike \(\oplus_n\) or \(\mathrm{ADDR}_k\) there is no evidence that the log factor is needed. FRPU94
ADDRESS / multiplexer total \(\Theta(k\log k)\)· putative Upper: $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log\mathrm{R}(f))$ by repeating each query $O(\log k)$ times. Lower: $\mathrm{N}_p(f) = \Omega(\mathrm{I}(f)\log\mathrm{I}(f))$ [GLX26noisy] with $\mathrm{I}(f) = (k+2)/2$. The two meet, so the multiplexer joins \(\oplus_n\) and \(\mathrm{Nav}_k\) as a family where the repetition log factor is provably necessary -- unsurprisingly, since a single corrupted address bit sends the walk to an unrelated table entry. GLX26noisy FRPU94
Binary tree navigation total \(\Theta(k\log k)\) Upper: $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ by repeating each query $O(\log k)$ times. Lower: $\mathrm{N}_p(f) = \Omega(\mathrm{I}(f)\log \mathrm{I}(f))$ [GLX26noisy] with $\mathrm{I}(f) = (k+1)/2$. The two meet, so navigation is a second natural family (after \(\oplus_n\)) where the repetition log factor is provably necessary. GLX26noisy FRPU94
TRIBES total \(\Omega(n),\ O(n\log n)\)· Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$. Upper: $O(\mathrm{R}\log\mathrm{R})$ by repeating each query. The influence-based bound $\mathrm{N}_p = \Omega(\mathrm{I}\log\mathrm{I})$ [GLX26noisy] gives only $\Omega(\log n\log\log n)$ here, since $\mathrm{I} = \Theta(\log n)$, so as at \(\mathrm{OMB}_n\) there is no evidence that the repetition log is needed. FRPU94 GLX26noisy
AND-OR tree (depth 2) total \(\Omega(n^2),\ O(n^2\log n)\) A noisy-query algorithm is in particular randomized, so $\mathrm{N}_p \ge \mathrm{R} = \Omega(n^2)$; repeating each query of an optimal randomized tree $O(\log \mathrm{R})$ times and taking majorities gives $\mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$ [FRPU94]. Whether the logarithm is needed here is open -- it is provably needed for \(\oplus_n\). FRPU94
NAND tree (balanced AND-OR formula) total \(\Omega(N^{\,0.753\ldots}),\ O\!\big(N^{\,0.753\ldots}\log N\big)\) Noisy queries can only cost more than clean ones, so $\mathrm{N}_p \ge \mathrm{R}$; majority-amplifying each query of the optimal randomized tree $O(\log \mathrm{R})$ times gives $\mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$ [FRPU94]. FRPU94
Recursive MAJORITY-of-3 total \(\Omega(2.59^{\,d}),\ O(d\,2.64944^{\,d})\) A noisy-query algorithm is randomized, so $\mathrm{N}_p \ge \mathrm{R} = \Omega(2.59^{\,d})$; amplifying each query of the optimal randomized tree by $O(\log \mathrm{R}) = O(d)$ repetitions gives $\mathrm{N}_p = O(\mathrm{R}\log \mathrm{R}) = O(d\,2.64944^{\,d})$ [FRPU94]. The whole $\mathrm{R}$ window is inherited, so the noisy exponent is open for exactly the same reason. FRPU94
Kushilevitz's function (iterated) total \(\Omega(N),\ O(N\log N)\) $\mathrm{N}_p \ge \mathrm{R} = \Omega(N)$, and majority-amplifying each of the $\mathrm{R}$ queries costs a $O(\log \mathrm{R})$ factor [FRPU94]. FRPU94
Rubinstein's function total \(\Omega(N),\ O(N\log N)\) $\mathrm{N}_p \ge \mathrm{R} = \Omega(N)$; amplifying each query $O(\log \mathrm{R})$ times gives the upper bound [FRPU94]. FRPU94
Ambainis-Sun function total \(\Omega(N),\ O(N\log N)\) $\mathrm{N}_p \ge \mathrm{R} = \Omega(N)$, and repeating each query $O(\log \mathrm{R})$ times gives $O(\mathrm{R}\log \mathrm{R})$ [FRPU94]. FRPU94
AND composed with NOT-EXACT-HALF total \(\Omega(n^2),\ O(n^2\log n)\) $\mathrm{N}_p \ge \mathrm{R} = \Omega(n^2)$, and majority-amplifying each query of the optimal randomized tree costs $O(\log \mathrm{R})$ [FRPU94]. FRPU94
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative A noisy-query algorithm is in particular a randomized one, so $\mathrm{N}_p \ge \mathrm{R} \ge 14011^{\,d}$. The matching $O(\mathrm{R}\log \mathrm{R})$ upper bound [FRPU94] is vacuous here, since no upper bound on $\mathrm{R}$ is known. FRPU94
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $g_{m,m}$: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$, and $\mathrm{R}=\widetilde\Theta(\sqrt n)$ there ($\widetilde O(\sqrt n)$ by [ABBLSS17, Thm 12], $\widetilde\Omega(\sqrt n)$ from $\mathrm{fbs}$). The noise overhead is inside the tilde. FRPU94
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$ with $\mathrm{R}=\widetilde\Theta(n)$; the noise overhead vanishes into the tilde. FRPU94
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{N}_p\ge\mathrm{R}=\widetilde\Omega(n^3)$; the $O(\mathrm{R}\log\mathrm{R})$ ceiling adds nothing because $\mathrm{R}$ has no recorded ceiling. FRPU94
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$, so the noisy model inherits the whole $\mathrm{R}$ range $[\widetilde\Omega(n^{4/3}),\widetilde O(n^2)]$. FRPU94
Gilmer-Saks-Srinivasan functions total \(\Omega(n)\) Squeeze: $\mathrm{N}_p\ge\mathrm{R}=\Omega(n)$; the ceiling $O(\mathrm{R}\log\mathrm{R})$ adds only $O(n^2\log n)$, which is above the recorded $\mathrm{R}$ ceiling anyway. FRPU94
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$, so the noisy model inherits the whole $\mathrm{R}$ range. FRPU94
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$ with $\mathrm{R}=\widetilde\Theta(n^{2/3})$ pinned; the noise overhead vanishes into the tilde. FRPU94
Ambainis' exact-quantum function total \(\widetilde\Theta(3^d)\) Floor $\mathrm{N}_p=\Omega(\mathrm{R})=\Omega(3^d)$ (a clean algorithm simulates the noisy one by flipping each answer itself with probability $p$), ceiling $\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})=O(d\,3^d)$ [FRPU94]. Whether the $\log$ is paid is open here: the general floor $\mathrm{N}_p=\Omega(\mathrm{I}\log\mathrm{I})$ only gives $\Omega(d\,(5/3)^d)$, because the total influence of $\mathrm{NE}^d$ is exponentially below its arity -- unlike $\oplus_n$, which is why that function is known to need $\Theta(n\log n)$. FRPU94
FORRELATION partial \(\widetilde\Theta(\sqrt n)\) At least $\mathrm{R}$, and at most $O(\mathrm{R})$ by reading each sampled coordinate $O(1)$ times and majority-voting.
k-FORRELATION partial \(\widetilde\Omega\!\big(n^{1-1/k}\big)\) Noise only makes the classical problem harder: $\mathrm{N}_p \ge \mathrm{R}$, and reading each sampled coordinate $O(1)$ times gives $\mathrm{N}_p = O(\mathrm{R})$ up to constants.
Simon's problem partial \(\Theta(2^{n/2})\) putative At least $\mathrm{R}$; and reading each sampled point $O(1)$ times and majority-voting each of the $n$ output bits costs only $O(\log n)$ per read, absorbed into the $\Theta(2^{n/2})$.
Deutsch-Jozsa partial \(\Theta(1)\) putative Read $O(1)$ fixed positions $O(1)$ times each and majority-vote away the noise.
Bernstein-Vazirani partial \(\widetilde\Theta(n)\) Faulty-oracle noise costs at most a log: $\mathrm{R} \le \mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$ with $\mathrm{R} = \Theta(n)$.
Unstructured search (relation) relation \(\Theta(n)\) At least $\mathrm{R} = \Theta(n)$; and reading each bit $O(1)$ times to beat the noise costs only a constant factor, so $\Theta(n)$.
FIND-1 under a density promise relation \(\Theta(1)\) putative Sample $O(1)$ random positions and read each $O(1)$ times to drive the noise below any constant: the promise means a random position is $1$ with probability $\ge 1/2$, so a constant number of noisy reads suffices.
Approximate Hamming weight relation \(\Theta(1)\) putative Reading $O(1/\varepsilon^2)$ random positions $O(1)$ times each still estimates the density to within $\varepsilon$, since the noise only rescales the empirical mean by a known factor $1-2p$.
Correlated-string search relation \(\Theta(\sqrt n)\) putative At constant noise rate $p$: read $c\sqrt n$ random coordinates once each and copy the (possibly corrupted) answers, guessing elsewhere. Expected agreement $n/2 + c(1/2-p)\sqrt n$, so $O(\sqrt n)$ noisy queries suffice, and $\mathrm{N}_p \ge \mathrm{R} = \Omega(\sqrt n)$. Note the contrast with $\mathrm{noisyR} = \Theta(1)$: the faulty-oracle model charges $1$ per query whatever the bias, and that single convention is the entire difference.
SearchCNF relation \(\Theta(1)\) putative Sample a clause and read each of its $k$ variables $O(1)$ times to beat the noise.
Gap-Majority partial \(\Theta(\min(n, 1/\delta^2))\) putative Read each sampled coordinate $O(1)$ times and majority-vote: $\mathrm{N}_p = O(\mathrm{R})$, and $\mathrm{N}_p \ge \mathrm{R}$ always.
Gap-Majority at constant gap partial \(\Theta(1)\) putative Between $\mathrm{R}$ and $O(\mathrm{R})$: read each sampled coordinate $O(1)$ times and vote.
Parity-labelled FIND-1 partial \(\Theta(1)\) putative Read each of $O(1)$ sampled positions $O(1)$ times and majority-vote: $\mathrm{N}_p = O(\mathrm{R})$, and $\mathrm{N}_p \ge \mathrm{R}$ always.
Approximate index partial \(\Theta(\sqrt{k\log k})\) putative At least $\mathrm{R}$; and reading each of the $O(\sqrt{k\log k})$ address bits $O(1)$ times and majority-voting still lands inside the ball, so $O(\mathrm{R})$. Note the sharp contrast with \(\mathrm{noisyR}(f)\) $= O(\log k)$: $\mathrm{N}_p$ charges a fixed constant noise rate per read, while the noisy-query model lets the algorithm buy an arbitrarily weak bias at cost $\gamma^2$, and weak bias is exactly what this problem needs.
Collision problem partial \(\widetilde\Theta(\sqrt n)\) Between $\mathrm{R}$ and $O(\mathrm{R}\log\mathrm{R})$: repeat each read $O(\log n)$ times to make the whole transcript reliable.
Element distinctness total \(\widetilde\Theta(n)\) Sandwiched: $\mathrm{R} \le \mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$, with $\mathrm{R} = \Theta(n)$. Setting the noise rate to $0$ recovers the ordinary model, and majority-voting each read $O(\log n)$ times is the generic upper bound.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) At least $\mathrm{R}$: setting the noise rate to $0$ recovers the ordinary model. Above, $\mathrm{N}_p = O(\mathrm{R}\log\mathrm{R}) = \widetilde O(n)$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$: setting the noise rate to $0$ recovers the ordinary model.
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) At least $\mathrm{R} = 2^{\Omega(n)}$; noise cannot help.
Surjectivity total \(\tilde\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(n\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
$k$-distinctness total \(\tilde\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(n\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
Triangle finding total \(\tilde\Theta(m^2)\) Between $\mathrm{R} = \Theta(m^2)$ and $O(\mathrm{R}\log \mathrm{R}) = O(m^2\log m)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Classically the problem is already maximally hard, so noise costs only a log.
Recursive Fourier sampling partial \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) At least $\mathrm{R} = n^{\Omega(\log n)}$, and at most $O(\mathrm{R}\log \mathrm{R})$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), which changes nothing at this scale. Noise is not what makes recursive Fourier sampling hard classically.
Welded trees relation \(\tilde\Theta(2^{n/2})\) At least $\mathrm{R} = \Omega(2^{n/2}/n)$, at most $O(\mathrm{R}\log \mathrm{R}) = O(2^{n/2}n^2)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Noise costs only a factor $\mathrm{poly}(n)$, which is invisible at this scale.
Local search on the hypercube relation \(\tilde\Theta(2^{n/2})\) Between $\mathrm{R} = \Theta(2^{n/2}\sqrt n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(2^{n/2}n^{1.5})$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). The integer cells are read bit by bit under noise, but that only costs $\mathrm{polylog}$.
Local search on the grid relation \(\tilde\Theta(k^{d/2})\ (d \ge 4)\) Between $\mathrm{R} = \Theta(k^{d/2})$ and $O(\mathrm{R}\log \mathrm{R}) = O(k^{d/2}\log k)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
Fourier fishing relation \(\tilde\Theta(N)\) Between $\mathrm{R} = \Omega(N/\log N)$ and $O(\mathrm{R}\log \mathrm{R}) = O(N\log N)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
Ordered search partial \(\tilde\Theta(\log n)\) Between $\mathrm{R} = \log_2 n - \Theta(1)$ and $O(\mathrm{R}\log \mathrm{R}) = O(\log n\log\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Whether the $\log\log n$ is real is the noisy-binary-search question of Feige-Raghavan-Peleg-Upfal.
Tseitin search on an expander relation \(\tilde\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(n\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
Inner product mod 2 total \(\Theta(n\log n)\) Pinned from both sides. Lower: $\mathrm{N}_p(f) = \Omega(\mathrm{I}(f)\log \mathrm{I}(f))$ [GLX26noisy] with $\mathrm{I} = n/2$. Upper: $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ with $\mathrm{R} = \Theta(n)$. IP therefore pays the same $\log$ tax as \(\oplus_n\), and for the same reason -- its influence is maximal. GLX26noisy FRPU94
Minsky-Papert one-in-a-box total \(\Omega(m^3),\ O(m^3\log m)\) Between $\mathrm{R} = \Theta(m^3)$ and $O(\mathrm{R}\log \mathrm{R})$. The influence-based lower bound $\mathrm{N}_p = \Omega(\mathrm{I}\log \mathrm{I})$ [GLX26noisy] is useless here, $\mathrm{I}$ being exponentially small, so the zoo does not know whether the $\log$ is needed -- in sharp contrast to \(\mathrm{IP}_n\) and \(\oplus_n\).
Sink of a tournament total \(\Omega(m),\ O(m\log m)\) Between $\mathrm{R} = \Theta(m)$ and $O(\mathrm{R}\log \mathrm{R})$. The influence-based lower bound $\mathrm{N}_p = \Omega(\mathrm{I}\log \mathrm{I})$ [GLX26noisy] gives nothing, $\mathrm{I}$ being exponentially small.
Scorpion graphs total \(\Omega(m),\ O(m\log m)\) Generic: $\mathrm{R}(f) \le \mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ [FRPU94], with $\mathrm{R} = \Theta(m)$. The $\mathrm{I}\log \mathrm{I}$ lower bound is useless here, the scorpion's total influence being exponentially small. FRPU94
Graph connectivity total \(\Omega(m^2),\ O(m^2\log m)\) Generic: $\mathrm{R}(f) \le \mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ [FRPU94], with $\mathrm{R} = \Theta(m^2)$. Whether the logarithm is needed is exactly the question of whether noisy connectivity is harder than noiseless; the $\mathrm{I}\log\mathrm{I}$ lower bound gives nothing, $\mathrm{I}(f)$ being exponentially small. FRPU94