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.
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 | \(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 |