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