Q The Query Complexity Zoo

Two different noisy query models

N_p (faulty oracle) and noisyR (bias purchasing) are NOT the same measure. Read this before using either.

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.