Q The Query Complexity Zoo
\(\mathrm{R}_{0}(f)\)

Zero-error randomized query complexity

Expected number of queries of a randomized algorithm that is always correct.

also written: Las Vegas query complexity, ZPP-style query complexity

Definition

The minimum over always-correct randomized algorithms of the worst-case expected number of queries. (Worst-case cost would collapse to $\mathrm{D}$, so the expected-cost convention is forced here.) Equivalently the algorithm may output "don't know" with probability $\le 1/2$ and otherwise must be right ("Las Vegas").

Basic facts

  • $\mathrm{R}(f) \le \mathrm{R}_0(f) \le \mathrm{D}(f)$.
  • $\mathrm{D}(f) = O(\mathrm{R}_0(f)^2)$ for total $f$; tight up to $\tilde\Omega$ by pointer functions [ABBLSS17].
  • $\mathrm{R}_0(f) = O\big(\mathrm{R}(f)^2\log \mathrm{R}(f)\big)$ [KulkarniTal16], improving $O(\mathrm{R}(f)^2\log n)$ [Midrijanis05].
  • $\mathrm{R}_0(\text{NAND-tree}_n) = \Theta(n^{0.7537\ldots})$ [Saks-Wigderson], matching $\mathrm{R}$ [Santha].

Relations to other measures

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

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

Known values

FunctionValueNotes
OR total \(n\)
AND total \(n\)
PARITY total \(n\)
MAJORITY total \(\Theta(n)\) Between $\mathrm{R}=\Theta(n)$ and $\mathrm{D}=n$. (The saving from stopping early once one side reaches $(n+1)/2$ is only $\Theta(\sqrt n)$.)
Threshold total \(\Theta(n)\)
Symmetric functions (general) total \(\Theta(n)\) Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$.
EXACT-HALF total \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(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{s}(f) \le \mathrm{R}_{0}(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}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(k)$ and $\mathrm{D}(f) = k$ here.
TRIBES total \(\Theta(n)\) Between $\mathrm{R}=\Theta(n)$ and $\mathrm{D}=n$.
AND-OR tree (depth 2) total \(\Theta(n^2)\)
NAND tree (balanced AND-OR formula) total \(\Theta\!\big(N^{\,0.753\ldots}\big)\) The exponent is $\log_2\!\frac{1+\sqrt{33}}{4} = 0.75366\ldots$. Upper bound [SaksWigderson86], matching lower bound [SaksWigderson86]; [Santha95] extends the lower bound to bounded error. SaksWigderson86 Santha95
Recursive MAJORITY-of-3 total \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) Identical to the bounds on $\mathrm{R}$: the interleaved algorithm of [MNSSTX16, Thm 4.2] that gives the upper bound is zero-error, and the lower bound applies a fortiori. So recursive majority is one of the functions where zero error is known to be free. GoosJayram16 MNSSTX16
Kushilevitz's function (iterated) total \(N\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $N$ here.
Rubinstein's function total \(\Theta(N)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here.
Ambainis-Sun function total \(\Theta(N)\) Sandwiched: $\mathrm{bs} \le \mathrm{R}_0 \le \mathrm{D}$, with both ends $\Theta(N)$.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative $\mathrm{R}_0 \ge \mathrm{R} = \Omega(\mathrm{bs})$; in fact $\mathrm{R}_0 \ge \mathrm{C} \ge \mathrm{bs}$ directly, since a zero-error algorithm must output a certificate.
Pointer functions total \(\widetilde O(\sqrt n)\) Variant $f_{2m,m}$ [ABBLSS17, Thm 4, Cor. 7]: $\widetilde O(m)$ cell queries on a grid of $2m^2$ cells, i.e. $\widetilde O(\sqrt n)$ bit queries. The back pointers let the Las Vegas algorithm halve the number of candidate zeroes each round. ABBLSS17
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{R}\le\mathrm{R}_0\le\mathrm{D}$.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{R}_0\ge\mathrm{R}\ge\mathrm{Q}$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$ and both ends are $\widetilde\Theta(n^2)$. A zero-error algorithm outputs a certificate, so certificate complexity is a lower bound on $\mathrm{R}_0$ even when it is far above $\mathrm{R}$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$. A zero-error algorithm's transcript is a certificate, so the maximal $\mathrm{C}_0$ pins $\mathrm{R}_0$ at the top; the cheap fractional certificate helps only the bounded-error models.
Random-indicator gadget total \(\Theta(n)\) Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$, and both ends are $\widetilde\Theta(n)$. A zero-error algorithm's transcript is a certificate, so the maximal $\mathrm{C}_0$ recorded above already pins $\mathrm{R}_0$ at the top even though $\mathrm{R}$ may be far smaller.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Squeezed between $\mathrm{R}$ and $\mathrm{D}$, both $\widetilde\Theta(n^{2/3})$.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{R}\le\mathrm{R}_0\le\mathrm{D}$.
FORRELATION partial \(\widetilde\Omega(\sqrt n)\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, i.e. between $\widetilde\Theta(\sqrt n)$ and $\Theta(n)$.
k-FORRELATION partial \(\widetilde\Omega\!\big(n^{1-1/k}\big)\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, i.e. between $\widetilde\Omega(n^{1-1/k})$ and $O(kn)$.
Simon's problem partial \(\Theta(2^{n/2})\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, both ends $\Theta(2^{n/2})$.
Deutsch-Jozsa partial \(N/2+1\) putative Zero error means every run ends on a certificate, and on a constant input that is $N/2+1$ queries; $\mathrm{R}_0 \le \mathrm{D}$ gives the match. So the $\mathrm{R}=O(1)$ upper bound is entirely a bounded-error phenomenon -- a clean $\mathrm{R}_0$ vs $\mathrm{R}$ separation of unbounded ratio for a partial function.
Bernstein-Vazirani partial \(n\) putative Zero error forces a spanning query set on every run, and $\mathrm{R}_0 \le \mathrm{D} = n$.
Unique search partial \(\Theta(n)\) Squeezed: $\mathrm{R} \le \mathrm{R}_0 \le \mathrm{D}$, and both ends are $\Theta(n)$.
Two-or-none search partial \(\Theta(n)\) Squeezed: $\mathrm{R} \le \mathrm{R}_0 \le \mathrm{D}$, and both ends are $\Theta(n)$.
Marked bit partial \(\Theta(n)\) Squeezed: $\mathrm{R} \le \mathrm{R}_0 \le \mathrm{D}$, and both ends are $\Theta(n)$.
Dense marked bit partial \(\Theta(1)\) putative At most $4$. Pick a uniformly random cell $b$ and query $y_b$; if it is $1$, output $1$ -- correct with certainty, since by the promise no domain input carries marks of both colours. Otherwise query $z_b$; if it is $1$, output $0$. Otherwise the cell is blank: discard it and repeat with a fresh random cell. At least half the cells are marked, so each round succeeds with probability $\ge 1/2$ and costs $\le 2$ queries; the expected total is $\le 4$. The algorithm never answers without holding a mark, so it is zero-error, and \(\mathrm{R}_{0}(f)\) is the expected-cost measure, which is what makes this legal -- the worst-case count is $\Omega(n)$, since an unlucky run can sample every blank cell first.
Unstructured search (relation) relation \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
FIND-1 under a density promise relation \(O(1)\) Zero error too: the algorithm verifies its own output, which is exactly why $\mathrm{R}_0=\Theta(\mathrm{R})$ for relations.
Approximate Hamming weight relation \(\Theta(n)\) putative After $q$ queries the unseen coordinates leave $|x|$ uncertain within a window of width $n-q$, so a never-wrong algorithm cannot stop before $q \ge (1-2\varepsilon)n$. This is the sharper statement: it is not just canonicity that costs, plain certainty already does.
Correlated-string search relation \(\Theta(n)\) putative The adversary argument applies to every tree in the support of a zero-error algorithm and to every leaf of it, so all leaves sit at depth $\ge n/2 + \sqrt n$ and even the expected cost is $\Omega(n)$. So $\mathrm{R}_0/\mathrm{R} = \Theta(\sqrt n)$ here: a second unbounded gap, for the same reason as at \(\mathrm{ApproxHW}\) -- there is no witness to verify.
SearchCNF relation \(\Theta(1)\) The witness is self-verifying (read the clause's $k$ variables and check), so the sampling algorithm can be made never-wrong by repeating until it succeeds: $\mathrm{R}_0 = \Theta(\mathrm{R}) = \Theta(1)$. Contrast \(\mathrm{ApproxHW}\), where there is no witness and $\mathrm{R}_0$ jumps to $\Theta(n)$.
Gap-Majority partial \(\Theta(n)\) putative A zero-error run must end on a certificate, so $\mathrm{R}_0 \ge \mathrm{C} = \Theta(n)$; and $\mathrm{R}_0 \le \mathrm{D}$. At constant $\delta$ this is an unbounded $\mathrm{R}_0$-vs-$\mathrm{R}$ gap.
Gap-Majority at constant gap partial \(\Theta(n)\) putative A zero-error run must end on a certificate, so $\mathrm{R}_0 \ge \mathrm{C} = \Theta(n)$; and $\mathrm{R}_0 \le \mathrm{D}$. Against $\mathrm{R} = \Theta(1)$ this is the unbounded $\mathrm{R}_0$-vs-$\mathrm{R}$ separation on partial functions.
Parity-labelled FIND-1 partial \(\Theta(1)\) putative At most $4$. Query uniformly random unqueried positions until one returns $1$, then report the parity of its index -- which is certain, since a single $1$ pins the side of the promise. A random position is $1$ with probability $n/4 \,/\, n$, so sampling without replacement finds one after $(n+1)/(n/4+1) < 4$ expected queries, and the algorithm never errs. Note this is the expected-cost convention (\(\mathrm{R}_{0}(f)\)); worst-case zero error would be $\mathrm{D}$ by definition, which is the whole content of the separation.
Approximate index partial \(\Theta(\sqrt{k\log k})\) Sandwiched: $\mathrm{R} \le \mathrm{R}_0 \le \mathrm{D}$, and the two ends agree.
Collision problem partial \(n/2+1\) putative Zero error means finishing on a certificate, and certifying one-to-one-ness takes $n/2+1$ distinct answers (see $\mathrm{C}$). So $\mathrm{R}_0 = \Theta(\mathrm{R}^2)$ here: the birthday paradox is a bounded-error phenomenon and nothing else.
Element distinctness total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(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{D} = O(n)$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$.
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) At least $\mathrm{R}$.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The $\mathrm{s}$ end is itself an unpublished argument (see above), so this is only as good as that.
$k$-distinctness total \(\Theta(n)\)· Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(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}_{0}(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}_0$ and the [BernsteinVazirani97] bound on $\mathrm{R}$; capped above by $\mathrm{D} = O(n^{\ell})$.
Welded trees relation \(\tilde\Theta(2^{n/2})\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \tfrac32\mathrm{R}_0$ and $\mathrm{R}_0 \le \mathrm{D}$, and both ends are $\tilde\Theta(2^{n/2})$. The classical algorithm never gains from being allowed to err: it finds the EXIT by walking to it.
Local search on the hypercube relation \(\Theta(2^{n/2}\sqrt n)\) A candidate local minimum is verified with $\Delta = n$ further queries, so $\mathrm{R}_0 = O(\mathrm{R} + n)$, and $n \ll \mathrm{R}$ here. Same remark as on \(\mathrm{Find1}_{\ge n/2}\).
Local search on the grid relation \(\Theta(k^{d/2})\ (d \ge 4)\) A candidate local minimum is verified with $\Delta = 2d = O(1)$ further queries, so $\mathrm{R}_0 = O(\mathrm{R} + d)$; with $d$ constant this is $\Theta(k^{d/2})$. Same remark as on \(\mathrm{LS}(\{0,1\}^n)\).
Fourier fishing relation \(\Theta(N)\) putative Settled, unlike $\mathrm{R}$ itself: the $\log N$ window that is open for bounded error closes at zero error. Upper $\mathrm{R}_0 \le \mathrm{D} = N$. Lower: $\mathrm{C} = O(\mathrm{R}_0)$ (\(\mathrm{C}(f)\) vs \(\mathrm{R}_{0}(f)\)) -- fix the coins of a zero-error algorithm and the transcript it produces must force a valid answer, so it is a certificate -- and $\mathrm{C} \ge N/2$ by the row below. So $\mathrm{R}_0 \ge N/4$, and Fourier fishing separates $\mathrm{R}_0$ from $\mathrm{R}$ by at least the same $\log N$ that separates $\mathrm{R}$ from $\mathrm{D}$.
Ordered search partial \(\log_2 n \pm \Theta(1)\) Sandwiched: $\mathrm{R} \le \mathrm{R}_0 \le \mathrm{D}$, and both ends are $\log_2 n \pm O(1)$.
Tseitin search on an expander relation \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D} = \Theta(n)$.
Inner product mod 2 total \(n\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Squeezed between $\mathrm{R} = \Theta(N)$ and $\mathrm{D} = N$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R} = \Theta(m)$ and $\mathrm{D} = O(m)$ here.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\mathrm{R} = \Theta(N)$ and $\mathrm{D} = N$.
Ambainis–Iraids–Kokainis certificate cheat sheet total \(\Omega(n^2)\) C=Ω(n²); under the zoo’s expected-cost zero-error convention, R₀=Ω(C), so this retains an Ω bound rather than a literal coefficient-one inequality. AIK26