One-sided randomized queries with certain rejection
Negative inputs always reject; positive inputs accept with probability at least 2/3.
also written:
R_1 in Ambainis–Iraids–Kokainis 2026, RP query complexity
Definition
The minimum worst-case query count of a randomized algorithm that always rejects $0$-inputs and accepts each $1$-input with probability at least $2/3$. This is $\mathrm{R}_1$ in [AIK26, Section 2.1]. The zoo's existing \(\mathrm{R}^{1}(f)\) fixes the other error convention (certain acceptance on positive inputs); keeping separate ids prevents attaching the one-sided algorithm to the wrong function.
Basic facts
- $\mathrm{R}\le\mathrm{R}_{\mathrm{RP}}=O(\mathrm{R}_0)$.
- \(\mathrm{AIKuD}\) has $\mathrm{C}=\Theta(n^2)$ and $\mathrm{R}_{\mathrm{RP}}=\Theta(n)$ [AIK26, Theorem 2.2].
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{R}_{\mathrm{RP}}(f)\). “\(\mathrm{R}_{\mathrm{RP}}(f)\) in terms of it” is the pair with \(\mathrm{R}_{\mathrm{RP}}(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 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(n)\) | The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26 |
| AND total | \(\Theta(n)\) | The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26 |
| PARITY total | \(\Theta(n)\) | The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26 |
| MAJORITY total | \(\Theta(n)\) | The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26 |
| Ambainis–Iraids–Kokainis unambiguous DNF total | \(\Theta(n)\) | Theorem 2.2; accepts only after a term is verified. AIK26 |