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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |