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

Noisy randomized query complexity

Randomized complexity when the algorithm may buy a biased (noisy) copy of any bit at cost proportional to bias squared.

Definition

In the noisy query model the algorithm may, at any step, request the value of $x_i$ through a channel of its choosing with bias $\gamma$, paying cost $\Theta(\gamma^2)$. (Equivalently: it may make a fractional query.) $\mathrm{noisyR}(f)$ is the least total cost of an algorithm that computes $f$ with error $\le 1/3$.

Ben-David and Blais showed this is exactly the right outer measure for composition.

Basic facts

  • $\mathrm{noisyR}(f) \le \mathrm{R}(f)$ always, and the two are not within a constant: $\mathrm{R}$ can be exponentially larger for partial $f$ (\(\mathrm{ApproxIndex}_k\)). Whether $\mathrm{R} = 2^{O(\mathrm{noisyR})}$ in general is open.
  • $\mathrm{R}(f\circ g^n) = \Omega(\mathrm{noisyR}(f)\,\mathrm{R}(g))$, and $\mathrm{noisyR}$ is the largest measure with this property [BenDavidBlais20composition].
  • Characterisation: $\mathrm{noisyR}(f) = \Theta\!\big(\mathrm{R}(f\circ \mathrm{GapMaj}_n)/\mathrm{R}(\mathrm{GapMaj}_n)\big)$.
  • If $\mathrm{R}(f) = \Theta(n)$ then $\mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$.
  • Lemma 37 of [BenDavidBlais20composition]: $\mathrm{noisyR}(f) = \Omega(1)$ for every non-constant $f$, and more precisely distinguishing two inputs that differ on a block $B$ costs $\Omega(1)$ inside $B$. Both hold for relations with two inputs whose allowed output sets are disjoint.
  • Lemma 38: $\mathrm{noisyR}(f) = \Omega(\mathrm{fbs}(f))$, by LP-weighting the previous item over the sensitive blocks. Composed with $\mathrm{R} = O(\mathrm{fbs}^3)$ this gives a complexity-only bound for total $f$. The new input-size-dependent bound is $\mathrm{R}=O(\mathrm{noisyR}\log(n+1))$ for partial Boolean functions [PednekarPodder26STOC].
  • Normal form (Lemmas 36, Theorem 39): an optimal noisy algorithm may be assumed to use only two bias values, $\gamma = 1$ and $\gamma = 1/\sqrt n$.
  • For every nonconstant partial Boolean $f$ on $n$ bits, $\mathrm{R}(f)\le C\log(n+1)\mathrm{noisyR}(f)$ [PednekarPodder26STOC, Theorem 31]. This closes Is …?. Total functions nevertheless have $\mathrm{R}/\mathrm{noisyR}=\Omega((\log N)^{1/4}/\log\log\log N)$ [Meiburg26composition, Theorem 4.1].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{noisyR}(f)\). “\(\mathrm{noisyR}(f)\) in terms of it” is the pair with \(\mathrm{noisyR}(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{noisyR}(f)\) in terms of it It in terms of \(\mathrm{noisyR}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total1.1,3 partialexp,? relation∞ open pair →
\(\mathrm{LR}(f)\) Linearised randomized complexity total1,2 partial1,2 derived open pair → total1,3 partialexp,? derived open pair →
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity total1,1 partial1,1 relation1,1 derived open pair → total1.1,3 partialexp,? relation∞ derived open pair →
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity total1,1 partial1,1 relation1,1 open pair → totalexp,? partialexp,? relationexp,? open pair →
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate total1,2 partial1,? derived open pair → total1,3 partial1,? derived open pair →
\(\mathrm{fbs}(f)\) Fractional block sensitivity total2,3 partial2,? derived open pair → total1,1 partial1,1 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)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
AND total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
PARITY total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
MAJORITY total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
Threshold total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. Fractional queries buy nothing at the top of the range. CKMPSS23
Symmetric functions (general) total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help. CKMPSS23
EXACT-HALF total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
ODD-MAX-BIT total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
ADDRESS / multiplexer total \(\Theta(k)\) From $\mathrm{R}(f) = \Theta(k) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. CKMPSS23
Binary tree navigation total \(\Theta(k)\) From $\mathrm{R}(f) = \Theta(k) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. CKMPSS23
TRIBES total \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
AND-OR tree (depth 2) total \(\Theta(n^2)\) Always $\mathrm{noisyR} \le \mathrm{R}$, and the recorded implication $\mathrm{R}(f) = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ applies, since $\mathrm{R} = \Theta(n^2) = \Theta(N)$. So the composition theorem $\mathrm{R}(F\circ f^m) = \Omega(\mathrm{noisyR}(F)\,\mathrm{R}(f))$ loses nothing when this function is the outer one. CKMPSS23
Kushilevitz's function (iterated) total \(\Theta(N)\) $\mathrm{noisyR} \le \mathrm{R}$ always, and the recorded implication $\mathrm{R}(f) = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ applies since $\mathrm{R} = \Theta(N)$. CKMPSS23
Rubinstein's function total \(\Theta(N)\) $\mathrm{noisyR} \le \mathrm{R}$, and $\mathrm{R} = \Theta(N)$ equals the arity, which forces $\mathrm{noisyR} = \Theta(\mathrm{R})$ by the recorded implication [CKMPSS23]. BenDavidBlais20composition CKMPSS23
Ambainis-Sun function total \(\Theta(N)\) $\mathrm{noisyR} \le \mathrm{R}$, and $\mathrm{R} = \Theta(N)$ is of the order of the arity, which forces equality up to constants by the recorded implication [CKMPSS23]. BenDavidBlais20composition CKMPSS23
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) $\mathrm{noisyR} \le \mathrm{R}$ always, and here $\mathrm{R} = \Theta(n^2) = \Theta(N)$ is of the order of the arity, which forces $\mathrm{noisyR} = \Theta(\mathrm{R})$ by the recorded implication [CKMPSS23]. BenDavidBlais20composition CKMPSS23
Ambainis' exact-quantum function total \(3^d\) The zoo's own \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) entry records $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23], and the recorded $\mathrm{R}$ is linear in the arity here -- the all-zero input has full sensitivity. CKMPSS23
FORRELATION partial \(\widetilde O(\sqrt n)\) At most $\mathrm{R}$. The reverse direction is only $\mathrm{R} = 2^{\Omega(\mathrm{noisyR})}$, which permits $\mathrm{noisyR}$ to be as small as $\Omega(\log n)$; cf. \(\mathrm{ApproxIndex}_k\), where that exponential gap is realised.
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) At most $\mathrm{R}$.
Simon's problem partial \(O(2^{n/2})\) At most $\mathrm{R}$.
Deutsch-Jozsa partial \(\Theta(1)\) At most $\mathrm{R} = O(1)$, and at least $1$.
Bernstein-Vazirani partial \(O(n)\) $\mathrm{noisyR} \le \mathrm{R} = O(n)$. The strengthening "$\mathrm{R} = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$" does not apply: the arity is $2^n$, not $n$.
Dense marked bit partial \(\Theta(1)\) At most $O(\mathrm{R}\log \mathrm{R}) = O(1)$, and at least $\mathrm{R} = \Theta(1)$.
Unstructured search (relation) relation \(\Theta(n)\) putative Upper: $\mathrm{noisyR} \le \mathrm{R} = \Theta(n)$. Lower: $\mathrm{R}$ is linear in the arity, the regime where fractional queries cannot help. Directly: let $\Gamma_i$ be the total squared bias the algorithm spends on coordinate $i$, so the cost is $\sum_i \Gamma_i$. The transcript distributions on $0^n$ and on $e_i$ have KL divergence $O(\Gamma_i)$, so distinguishing $0^n$ from $e_i$ needs $\Gamma_i = \Omega(1)$; this must hold for every $i$, giving cost $\Omega(n)$. CKMPSS23
FIND-1 under a density promise relation \(\Theta(1)\) At most $\mathrm{R} = O(1)$, and at least $1$: buying bias cannot help a problem that is already solved by one full-strength query.
Approximate Hamming weight relation \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$, and at least $1$.
Correlated-string search relation \(\Theta(1)\) Buy every coordinate at bias $c/\sqrt n$ and set $y$ to the answers: total cost $n \cdot c^2/n = c^2 = O(1)$, and the expected agreement is $n/2 + c\sqrt n/2$, one standard deviation past the promise for large enough $c$. The lower bound $\Omega(1)$ is Lemma 37 of [BenDavidBlais20composition], which applies because $x=0^n$ and $x=1^n$ have disjoint sets of allowed outputs. BenDavidBlais20composition GLSS19
SearchCNF relation \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$, and at least $1$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta^2))\) putative Equal to $\mathrm{R}$: buying bias buys nothing here, which is exactly why $\mathrm{GapMaj}$ is the universal inner function of [CKMPSS23] (Theorem 4: $\mathrm{noisyR}(f) = \Theta(\mathrm{R}(f \circ \mathrm{GapMaj}_n)/n)$, with their $\mathrm{GapMaj}_n$ the $\delta = 2/\sqrt{n}$ instance). Upper: $\mathrm{noisyR} \le \mathrm{R}$ always. Lower: let $\mu^{\pm}$ be uniform on the two Hamming levels, so each coordinate is marginally $\mathrm{Bern}(1/2 \pm \delta)$. A noisy query of bias $\gamma$ returns a bit distributed $\mathrm{Bern}(1/2 \pm \gamma\delta)$, and $\mathrm{KL} = O(\gamma^2\delta^2)$, while the query costs $\gamma^2$. Distinguishing $\mu^+$ from $\mu^-$ needs $\Omega(1)$ total divergence, so the cost $\sum_j \gamma_j^2$ is $\Omega(1/\delta^2)$. CKMPSS23
Gap-Majority at constant gap partial \(\Theta(1)\) putative Equal to $\mathrm{R}$: buying bias buys nothing here. See \(\mathrm{GapMaj}^{\delta}_{n}\). CKMPSS23
Parity-labelled FIND-1 partial \(\Theta(1)\) At most $\mathrm{R} = O(1)$, and at least $1$: there is nothing for cheap low-bias queries to buy.
Approximate index partial \(O(\log k) = O(\log\log n)\) Not stated as a value in the source, but it is exactly what its two theorems say. Their composed algorithm gives $\mathrm{R}(\mathrm{ApproxIndex}_k \circ \mathrm{GapMaj}_k) = O(k\log k)$, and Theorem 3 says $\mathrm{R}(f \circ g) = \Omega(\mathrm{noisyR}(f)\,\mathrm{R}(g))$ with $\mathrm{R}(\mathrm{GapMaj}_k) = \Theta(k)$; divide. Directly, in the noisy model: buy each of the $k$ address bits at bias $\gamma = c\sqrt{\log k/k}$ for $\gamma^2$ each, total $c^2\log k$, which puts the guess inside the ball with high probability, then read one array cell at bias $1$. BenDavidBlais20composition
Collision problem partial \(O(\sqrt n)\) $\mathrm{noisyR} \le \mathrm{R}$. The implication "$\mathrm{R} = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$" does not apply, since $\mathrm{R} = \Theta(\sqrt n)$ and the arity is $n$.
Element distinctness total \(\Theta(n)\)· Upper: $\mathrm{noisyR} \le \mathrm{R}$. Lower: the recorded $\mathrm{R} = \Theta(n)$ is linear in the arity, and the zoo entry for \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) records $\mathrm{R}(f)=\Theta(n) \Rightarrow \mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ -- at the top of the range there is no room for fractional queries. Contrast \(\mathrm{COL}_n\), where $\mathrm{R} = \Theta(\sqrt n)$ and the shortcut is unavailable. CKMPSS23
Ambainis-Belovs function partial \(O(n)\) At most $\mathrm{R} = O(n)$. The shortcut $\mathrm{R} = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$ is unavailable: only $\mathrm{R} = \Omega(n^{1/3})$ is known.
Surjectivity total \(\Theta(n)\) $\mathrm{noisyR}\le\mathrm{R}=\Theta(n)$ [BenDavidBlais20composition], and here $\mathrm{R}=\Theta(n)$ is $\Theta(\text{arity})$, which forces $\mathrm{noisyR}=\Theta(\mathrm{R})$ [CKMPSS23]. Cheap biased queries do not help: the hard part is coverage, not accuracy. CKMPSS23 BenDavidBlais20composition
$k$-distinctness total \(\Theta(n)\) $\mathrm{noisyR}\le\mathrm{R}$ [BenDavidBlais20composition], and $\mathrm{R}=\Theta(n)=\Theta(\text{arity})$ forces equality [CKMPSS23]. CKMPSS23 BenDavidBlais20composition
Triangle finding total \(\Theta(m^2)\) $\mathrm{noisyR}\le\mathrm{R}$ [BenDavidBlais20composition], and $\mathrm{R}=\Theta(m^2)=\Theta(\text{arity})$ forces $\mathrm{noisyR}=\Theta(\mathrm{R})$ [CKMPSS23]. CKMPSS23 BenDavidBlais20composition
Ordered search partial \(O(\log n)\) $\mathrm{noisyR}\le\mathrm{R}=O(\log n)$ [BenDavidBlais20composition]. The strengthening "$\mathrm{R}=\Theta(\text{arity})\Rightarrow\mathrm{noisyR}=\Theta(\mathrm{R})$" does not apply: the arity is $n$, not $\log n$. Noisy binary search is the natural candidate for a matching lower bound, but the answer here is a single bit, so the information-per-cost argument gives only $\Omega(1)$. BenDavidBlais20composition
Inner product mod 2 total \(\Theta(n)\) The zoo's own \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) entry records $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23], and the recorded $\mathrm{R}$ is linear in the arity here -- the function reads all $n$ bits, so buying unbiased copies buys nothing. CKMPSS23
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) The zoo's own \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) entry records $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23], and the recorded $\mathrm{R}$ is linear in the arity here -- the AND-OR tree is evasive even for randomised algorithms. CKMPSS23
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) putative The zoo's shortcut $\mathrm{R} = \Theta(n) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$ does not apply -- $\mathrm{R} = \Theta(\sqrt N)$ here, not linear in the arity -- so the lower bound has to come from a restriction. Fix the tournament on $\{2,\dots,m\}$ to be transitive and orient $\{1,m\}$ into vertex $1$: then every vertex except $1$ has an outgoing edge, and the function of the $m-2$ free edges $\{1,u\}$ is exactly $\mathrm{AND}_{m-2}$. Noisy randomized complexity is monotone under restriction, and $\mathrm{noisyR}(\mathrm{AND}_k) = \Theta(k)$ since $\mathrm{R}(\mathrm{AND}_k) = k$ is linear in its arity. Upper: $\mathrm{noisyR} \le \mathrm{R} = \Theta(m)$ (\(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
Scorpion graphs total \(\Theta(m) = \Theta(\sqrt N)\) putative As on \(\mathrm{SINK}_m\), the "$\mathrm{R}$ linear in the arity" shortcut is unavailable ($\mathrm{R} = \Theta(\sqrt N)$), so the lower bound comes from a restriction to $\mathrm{AND}$. Put the sting at $1$, the tail at $2$ and the body at $3$: fix $\{1,2\}$ and $\{2,3\}$ present, every other edge at $1$ or $2$ absent, and every foot-foot edge absent. What remains free is the $m-3$ edges $\{3,u\}$, $u \ge 4$, and the graph is a scorpion iff all of them are present -- no other vertex can play body, since the feet now have degree $\le 1$. So $\mathrm{noisyR} \ge \mathrm{noisyR}(\mathrm{AND}_{m-3}) = \Theta(m)$, and $\mathrm{noisyR} \le \mathrm{R} = \Theta(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) The zoo's own \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) entry records $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23], and the recorded $\mathrm{R}$ is linear in the arity here -- connectivity is randomised-evasive up to a constant. CKMPSS23
Meiburg’s total noisy-query separation total \(O(q^{10}\log q\log\log q)\) Theorem 4.1: its upper bound is O(ℓ_q log(ℓ_q+2) u_q² q²). Meiburg26composition