The word "noisy" is used for two genuinely different things, and the zoo keeps them as separate measures.
1. Faulty oracle -- \(\mathrm{N}_{p}(f)\)
Introduced by [FRPU94] (see also [ReischukSchmeltz91]). Every query answer is independently flipped with probability $p$; the algorithm has no control over this. Cost = number of queries.
- $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f)/(1-2p)^2)$ -- repeat and majority-vote.
- $\mathrm{N}_p(\mathrm{PARITY}_n)=\Theta(n\log n)$: the $\log$ is necessary [FRPU94, EvansPippenger98].
- The quantum analogue \(\mathrm{Q}^{\mathrm{rob}}(f)\) behaves differently: $\mathrm{Q}^{\mathrm{rob}}(\mathrm{PARITY}_n)=\Theta(n)$ -- no log [BNRdW05].
2. Bias purchasing -- \(\mathrm{noisyR}(f)\)
Introduced by [BenDavidBlais20composition]. The algorithm may query a bit "at bias $\gamma$", receiving the correct value with probability $\tfrac12+\gamma$, and pays $\gamma^2$ for it (so an exact query costs $\Theta(1)$). The algorithm chooses the noise level per query.
- $\mathrm{noisyR}(f)\le\mathrm{R}(f)$.
- $\mathrm{noisyR}(f)=\Theta\big(\mathrm{R}(f\circ\mathrm{GapMaj}_n)/\mathrm{R}(\mathrm{GapMaj}_n)\big)$ -- an exact characterisation.
- $\mathrm{noisyR}$ is the largest measure $M$ with $\mathrm{R}(f\circ g^n)=\Omega(M(f)\mathrm{R}(g))$.
- There are partial $f$ with $\mathrm{R}(f)=\mathrm{noisyR}(f)^{1+\Omega(1)}$; this separation is the refutation of the randomized composition conjecture.
The difference in one line
In $\mathrm{N}_p$ the noise is imposed on the algorithm and the natural question is "how much repetition do you need?"; in $\mathrm{noisyR}$ the noise is bought by the algorithm and the natural question is "how little information suffices?". Their behaviour on $\mathrm{PARITY}$ already differs: $\mathrm{N}_p(\mathrm{PARITY}_n)=\Theta(n\log n)$ while $\mathrm{noisyR}(\mathrm{PARITY}_n)=\Theta(n)$ (since $\mathrm{R}(\mathrm{PARITY}_n)=\Theta(n)$ is full, and $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23]).
The information-theoretic engine, and what is open in it
Both halves of \(\mathrm{noisyR}^{\mathrm{na}}(f)\)'s Theorem 8 -- $\mathrm{noisyR}^{\mathrm{na}}(f) =\Theta(\mathrm{R}^{\mathrm{na}}(f))$ for total and partial $f$, but not for relations -- run on one inequality of [Samorodnitsky16], in the form isolated by [PolyanskiyWu17]: a noisy copy of $X$ at bias $\rho$ tells you at least as much about $f(X)$ as an erasure copy that survives with probability $\rho^2$. Since erasures are honest queries, a noise budget converts into a query budget.
That inequality is a by-product of the most informative Boolean function conjecture of [CourtadeKumar14]: if $Y$ is $X$ sent through a binary symmetric channel with crossover probability $\varepsilon$, then for every Boolean $f$, $$I\big(f(X);Y\big) \;\le\; 1 - H_2(\varepsilon),$$ with equality for a dictator (a subcube of codimension 1). It is open. [Samorodnitsky16] proves it for high noise -- there is an absolute $\delta>0$ such that it holds whenever $(1-2\varepsilon)^2\le\delta$ -- via the strengthening of Mrs. Gerber's lemma $\mathrm{Ent}(T_\varepsilon f)\le \mathbb{E}_T\,\mathrm{Ent}(f\mid T)$ that also yields the noise-beats-erasure comparison above.
The reason none of this survives for relations is the last step, not the first: converting an entropy gap into a guessing advantage needs Fano / [HellmanRaviv70], and with many acceptable outputs there is nothing to guess. That is exactly where the exponential separation of Theorem 8 lives.