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