Q The Query Complexity Zoo
\(\mathrm{R}^{1}(f)\)

One-sided-error randomized query complexity

Randomized complexity when errors are allowed on only one side.

also written: RP-style query complexity, R^0(f) for the co-version

Definition

$\mathrm{R}^1_\varepsilon(f)$: the algorithm must output $1$ with certainty when $f(x)=1$ and output $0$ with probability $\ge 1-\varepsilon$ when $f(x)=0$ (or vice versa for $\mathrm{R}^0$). This is the query analogue of $\mathsf{RP}$/$\mathsf{coRP}$, and $\mathrm{R}_0(f) = \Theta(\mathrm{R}^0(f) + \mathrm{R}^1(f))$ up to log factors (run both and stop when one is certain).

Parameters

\(\varepsilon\) (eps) default \(1/3\)

Basic facts

  • $\mathrm{R}^1(f) \ge \mathrm{C}^1(f)$: a certain "yes" must exhibit a 1-certificate.
  • $\mathrm{R}(f) \le \mathrm{R}^1(f) \le \mathrm{R}_0(f) \le \mathrm{D}(f)$.
  • The total complement \(\overline f_{\mathrm{AIK}}\) has $\mathrm{C}=\Theta((\mathrm{R}^{1})^2)$ with no logarithmic loss [AIK26, Theorem 2.2]. The original \(\mathrm{AIKuD}\) uses the paper’s certain-rejection $\mathrm{R}_1$, recorded here as \(\mathrm{R}_{\mathrm{RP}}(f)\).

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{R}^{1}(f)\). “\(\mathrm{R}^{1}(f)\) in terms of it” is the pair with \(\mathrm{R}^{1}(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{R}^{1}(f)\) in terms of it It in terms of \(\mathrm{R}^{1}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,2 partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total1,1 partial1,1 open pair → total2,2 partial2,? derived open pair →
\(\mathrm{C}^1(f)\) 1-certificate complexity total∞ partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity total1,2 partial∞ derived open pair → total1,1 partial1,1 derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
AND total \(n\) Sandwiched: $\mathrm{C}^1(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
PARITY total \(n\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Threshold total \(\Theta(n)\) Squeezed: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$.
Symmetric functions (general) total \(\Theta(n)\) Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
ADDRESS / multiplexer total \(k+1\) Sandwiched: $\mathrm{C}^1(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
Binary tree navigation total \(\Theta(k)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(k)$ and $\mathrm{D}(f) = k$ here.
TRIBES total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
AND-OR tree (depth 2) total \(\Theta(n^2)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta(n^2)$ here.
NAND tree (balanced AND-OR formula) total \(\Theta\!\big(N^{\,0.753\ldots}\big)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta\!\big(N^{\,0.753\ldots}\big)$ here.
Recursive MAJORITY-of-3 total \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) Between $\mathrm{R}_{\varepsilon}$ and $\mathrm{R}_0$, whose recorded windows coincide here.
Kushilevitz's function (iterated) total \(\Theta(N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $N$ here.
Rubinstein's function total \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here.
Ambainis-Sun function total \(\Theta(N)\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}^{1} \le \mathrm{R}_0$, with both ends $\Theta(N)$ here.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative Between $\mathrm{R}$ and $\mathrm{R}_0$, both $\ge 14011^{\,d}$ here.
Pointer functions total \(\widetilde O(\sqrt n)\) Variant $g_{m,m}$: the algorithm of [ABBLSS17, Thm 12] is stated for one-sided error, which is what the recorded $\mathrm{R}$ line quotes. ABBLSS17
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{D}$.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{R}^1\ge\mathrm{R}\ge\mathrm{Q}$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{R}_0$, i.e. between $\widetilde\Omega(n^{4/3})$ and $\widetilde\Theta(n^2)$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) Squeeze: $\mathrm{R}^1\ge\mathrm{R}=\Omega(n^2)$ by the line above; the ceiling is $\mathrm{D}=\Theta(n^2)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{R}^1\ge\mathrm{R}=\widetilde\Omega(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{D}$.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{D}$.
FORRELATION partial \(\widetilde\Omega(\sqrt n)\) Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\widetilde\Omega(\sqrt n)$ here.
k-FORRELATION partial \(\widetilde\Omega\!\big(n^{1-1/k}\big)\) Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\widetilde\Omega(n^{1-1/k})$ here.
Simon's problem partial \(\Theta(2^{n/2})\) Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\Theta(2^{n/2})$.
Deutsch-Jozsa partial \(N/2+1\) putative One-sided error does not help, even though the cheap side is only two queries. Fix coins $r$ for which the run on $0^N$ outputs $0$ -- at least $2/3$ of them do -- and let $L \le q$ be the positions it reads. If $L \le N/2$ some balanced $y$ agrees with all of them, so the same run outputs $0$ on a $1$-input, which zero error on the $1$-side forbids. Hence $q \ge N/2+1$, and $\mathrm{R}^1 \le \mathrm{R}_0 = N/2+1$. Compare $\mathrm{R} = O(1)$.
Bernstein-Vazirani partial \(\Theta(n)\) Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, and both ends are $\Theta(n)$ here.
Marked bit partial \(\Theta(n)\) Between $\mathrm{R}$ and $\mathrm{R}_0$, which agree.
Dense marked bit partial \(\Theta(1)\) Between $\mathrm{R}$ and $\mathrm{R}_0$, which agree.
Unstructured search (relation) relation \(\Theta(n)\) For a search problem, one-sided error means the algorithm never emits an invalid output, so it must be certain: outputting $\bot$ requires seeing all $n$ zeros. Hence $\mathrm{R}^1 = \Theta(\mathrm{R}_0) = \Theta(n)$, and it is squeezed by $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$ with both ends $\Theta(n)$ anyway.
FIND-1 under a density promise relation \(\Theta(1)\) Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0 = O(1)$. The promise $|x| \ge n/2$ means a random probe both finds and certifies a $1$, so never emitting an invalid output costs nothing extra -- in sharp contrast to \(\mathrm{SEARCH}_n\).
Approximate Hamming weight relation \(\Theta(n)\) putative For a search problem, one-sided error means the output is always valid. Every leaf that outputs some $w$ must have pinned $|x|/n$ to within $\varepsilon$ with certainty, which takes $(1-2\varepsilon)n$ queries; since every input reaches an outputting leaf with probability $\ge 2/3$, the cost is $\Omega(n)$. So $\mathrm{R}^1 = \Theta(\mathrm{R}_0) = \Theta(n)$, against $\mathrm{R} = \Theta(1)$ -- the same collapse that makes $\mathrm{R}_0$ jump.
SearchCNF relation \(\Theta(1)\) Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0 = \Theta(1)$. A falsified clause is self-certifying, so demanding a never-invalid output costs nothing.
Gap-Majority partial \(\Theta(n)\) Squeezed: $\mathrm{R}^1 \ge \mathrm{C}^1 = \Theta(n)$ (a certain "yes" must exhibit a $1$-certificate) and $\mathrm{R}^1 \le \mathrm{R}_0 = \Theta(n)$. One-sided error is already as expensive as no error at all.
Gap-Majority at constant gap partial \(\Theta(n)\) Squeezed between $\mathrm{C}^1$ and $\mathrm{R}_0$.
Parity-labelled FIND-1 partial \(\Theta(1)\) Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0 = O(1)$. Since the algorithm only ever answers from a $1$ it has seen, one-sided error costs nothing -- as at \(\mathrm{Find1}_{\ge n/2}\), and unlike \(\mathrm{GapMaj}^{\delta}_{n}\), where $\mathrm{R}^1 = \Theta(n)$.
Approximate index partial \(\Theta(\sqrt{k\log k})\) Squeezed between $\mathrm{R}$ and $\mathrm{R}_0$, which agree.
Collision problem partial \(\Theta(n)\) putative With $1$ = "two-to-one": an algorithm that is certain on the $1$-side never outputs $0$ on a two-to-one input, so whenever it does output $0$ it must hold a $0$-certificate, i.e. $n/2+1$ distinct values. It must do so with probability $\ge 2/3$ on one-to-one inputs, so $\mathrm{R}^1 = \Omega(n)$; and $\mathrm{R}^1 \le \mathrm{D} = n/2+1$.
Element distinctness total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Between $\mathrm{R} = \Omega(n^{1/3})$ and $\mathrm{R}_0 = O(n)$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) Squeezed from below by $\mathrm{R} \le \mathrm{R}^1$, with $\mathrm{R} = \widetilde\Omega(\sqrt n)$; above, $\mathrm{R}^1 \le \mathrm{R}_0$. The relational reading of one-sided error is available here because the search problem is total and its outputs are self-certifying.
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) Squeezed from below by $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, and both $\mathrm{R}$ and $\mathrm{R}_0$ are already $2^{\Omega(n)}$.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
$k$-distinctness total \(\Theta(n)\)· Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m^2)$ here.
Recursive Fourier sampling partial \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) From $\mathrm{R}_{\varepsilon} \le \mathrm{R}^{1}$; capped above by $\mathrm{D} = O(n^{\ell})$.
Ordered search partial \(\Theta(\log n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(\log n)$ here.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Sandwiched: $\mathrm{R}(f) \le \mathrm{R}^{1}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta(m^3) = \Theta(N)$ here.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) Sandwiched between $\mathrm{R} = \Theta(m)$ and $\mathrm{R}_0 = \Theta(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\mathrm{R} = \Theta(N)$ and $\mathrm{D} = N$.
Complement of the Ambainis–Iraids–Kokainis DNF total \(\Theta(n)\) R¹(¬f)=R_RP(f) under the catalog conventions. Theorem 2.2 gives the upper bound; C=O(R²) gives the matching lower bound. AIK26