Bounded-error randomized query complexity
Worst-case number of queries of a randomized decision tree that errs with probability at most eps.
also written:
R_2(f), Monte Carlo decision tree complexity, BPP-style query complexity
Definition
A randomized decision tree is a probability distribution over deterministic trees. $\mathrm{R}_\varepsilon(f)$ is the least $T$ such that some distribution over depth-$T$ trees outputs $f(x)$ with probability $\ge 1-\varepsilon$ for every $x$ in the domain. Unadorned $\mathrm{R}(f) := \mathrm{R}_{1/3}(f)$.
Two cost conventions circulate and they are not interchangeable at small bias:
- worst-case cost ($\mathrm{R}_\varepsilon$): every branch has depth $\le T$;
- expected cost ($\bar{\mathrm{R}}_\varepsilon$, see \(\bar{\mathrm{R}}_{\varepsilon}(f)\)): the expected number of queries is $\le T$, maximised over inputs.
Parameters
\(\varepsilon\) (eps) default \(1/3\)range \([0, 1/2)\)
Error probability. Standard choice 1/3; "small bias" means eps = 1/2 - gamma with gamma -> 0.
Amplification (always true): $\mathrm{R}_{\varepsilon}(f) = O\!\big(\mathrm{R}_{1/3}(f)\log(1/\varepsilon)\big)$ by majority vote, and this is tight for some $f$ (e.g. $\mathrm{OR}$) but not for all.
Small bias: for $\varepsilon = 1/2-\gamma$, $\mathrm{R}_{1/2-\gamma}(f) \ge \Omega(\gamma^2 \mathrm{R}_{1/3}(f))$ is false in general; the correct general statement is $\mathrm{R}_{1/3}(f) = O\!\big(\gamma^{-2}\,\mathrm{R}_{1/2-\gamma}(f)\big)$ by amplification, and the extent to which small-bias algorithms can beat $\gamma^2$ scaling is exactly what the measures \(\mathrm{noisyR}(f)\) and \(\mathrm{LR}(f)\) were invented to capture.
Detailed records: \(\mathrm{R}_{\varepsilon}(f) \text{ as } \varepsilon \to 0\)
Basic facts
- $\mathrm{bs}(f) \le 3\,\mathrm{R}(f)$ and $\widetilde{\deg}(f) \le \mathrm{R}(f)$ [Nisan; BBCMdW01].
- $\mathrm{D}(f) \le 27\,\mathrm{R}(f)^3$ [Nisan]. Best known separation is $\mathrm{D} = \tilde\Omega(\mathrm{R}^2)$ [ABBLSS17], so the truth is between $2$ and $3$.
- Composition can fail: there are partial $f,g$ with $\mathrm{R}(f\circ g) \ll \mathrm{R}(f)\mathrm{R}(g)$ [BenDavidBlais20composition].
- $\mathrm{R}_\varepsilon(f) = \max_\mu \mathrm{D}^\mu_\varepsilon(f)$ (Yao), for the worst-case-cost convention.
- Composition holds with an outer-input-size logarithmic loss, even for partial Boolean functions: $\mathrm{R}(f\circ g^n)=\Omega(\mathrm{R}(f)\mathrm{R}(g)/\log(n+1))$ [PednekarPodder26STOC]. Constant-factor composition fails even for total functions [Meiburg26composition]; see comp-R.
- The optimal total-function $\mathrm{R}$-versus-$\mathrm{Q}$ power is 4 [OpenAI26QuarticRQ]. The new family rules out every power below 4, matching $\mathrm{R}\le\mathrm{D}=O(\mathrm{Q}^4)$ [ABKRT21]; see \(F_{k,m}\).
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{R}_{\varepsilon}(f)\). “\(\mathrm{R}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{R}_{\varepsilon}(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 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(n)\) | |
| AND total | \(\Theta(n)\) | |
| PARITY total | \(n\) | |
| MAJORITY total | \(\Theta(n)\) | |
| Threshold total | \(\Theta(n)\) | $\mathrm{R}(f) = \Omega(\mathrm{bs}(f)) = \Omega(\max\{k,\;n-k+1\}) = \Omega(n)$. Note this holds uniformly in $k$, unlike $\mathrm{Q}$, which drops to $\Theta(\sqrt n)$ at the two ends. |
| Symmetric functions (general) total | \(\Theta(n)\) | Sandwiched: $\mathrm{bs}(f)/3 \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. Randomization never helps on a symmetric function, in sharp contrast with $\mathrm{Q}$, which drops to $\Theta(\sqrt n)$ when the jump is at the edge. |
| EXACT-HALF total | \(\Theta(n)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| ODD-MAX-BIT total | \(\Theta(n)\) | |
| ADDRESS / multiplexer total | \(\Theta(k)\) | At most $\mathrm{D}=k+1$, and at least $\mathrm{bs}/3 = \Omega(k)$. Nisan91 |
| Binary tree navigation total | \(\Theta(k)\) | At most $\mathrm{D}=k$. For the lower bound, on a uniformly random input each of the $k$ variables on the walk is sensitive with probability $1/2$, so $\mathrm{bs} = \Omega(k)$ and $\mathrm{R} \ge \mathrm{bs}/3$. |
| TRIBES total | \(\Theta(n)\) | |
| AND-OR tree (depth 2) total | \(\Theta(n^2)\) | SaksWigderson86 Snir85 |
| NAND tree (balanced AND-OR formula) total | \(\Theta\!\big(N^{\,0.753\ldots}\big)\) | Santha95 |
| Recursive MAJORITY-of-3 total | \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) | In terms of $N = 3^d$ that is between $N^{0.8663}$ and $N^{0.8869}$; the exact exponent is a well-known open problem. History of the lower bound: $(7/3)^d$ [JayramKumarSivakumar03] $\to 2.55^d$ [Leonardos13] $\to 2.57143^d$ [MNSSTX16] $\to 2.59^d$ [GoosJayram16], the last via \(\mathrm{cjdeg}_{\varepsilon}(f)\) rather than information complexity. The upper bound is the interleaved recursive algorithm of [MNSSTX16, Thm 4.2] and is zero-error, so it bounds $\mathrm{R}_0$ too. GoosJayram16 MNSSTX16 Leonardos13 JayramKumarSivakumar03 |
| Kushilevitz's function (iterated) total | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| Rubinstein's function total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}_{\varepsilon}(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{bs} \le \mathrm{R}_{\varepsilon} \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}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| Meiburg's tournament-subcube function total | \(\ge 14011^{\,d}\) putative | $\mathrm{R} = \Omega(\mathrm{bs})$, and $\mathrm{bs} \ge 14011^{\,d}$. |
| Pointer functions total | \(\widetilde O(\sqrt n)\) | Variant $g_{m,m}$ [ABBLSS17, Thm 12, Cor. 14], for which $\mathrm{R}_0 = \widetilde\Omega(n)$ -- this is the $\mathrm{R}_0$-vs-$\mathrm{R}$ separation, so the two $\widetilde O(\sqrt n)$ lines here are attained on different variants. Proved there for one-sided error, which dominates $\mathrm{R}$. ABBLSS17 |
| Cheat-sheet functions total | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{Q}\le\mathrm{R}\le\mathrm{D}$, both $\widetilde\Theta(n)$. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{R}\ge\mathrm{Q}$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3})\) | Squeeze: $\mathrm{R}=\Omega(\mathrm{fbs})$; the ceiling is $\mathrm{R}\le\mathrm{D}=\widetilde\Theta(n^2)$. |
| Gilmer-Saks-Srinivasan functions total | \(\Theta(n^2)\) putative | Not computed in [GSS16], and the fractional certificate leaves it open from below -- $\mathrm{fbs}=\Theta(n)$ only gives $\mathrm{R}=\Omega(n)$. But the family is an $\mathrm{OR}$-composition, so the randomized composition theorem applies: $\mathrm{R}(\mathrm{OR}_n\circ g_n^{\,n})=\Omega(\mathrm{R}(\mathrm{OR}_n)\,\chi(g_n))$ [Sanyal18] (comp-R), and $\chi(g_n)\ge(\mathrm{bs}(g_n)+1)/2$ [Li18, Thm 1] with $\mathrm{bs}(g_n)\ge\mathrm{s}(g_n)=n$, since a $1$-input of $g_n$ is an isolated point. So $\mathrm{R}=\Omega(n\cdot n)=\Omega(n^2)$, and $\mathrm{R}\le\mathrm{D}=n^2$. The cheap fractional certificate buys nothing after all: this family separates $\mathrm{C}$ from $\mathrm{RC}$ quadratically but not from $\mathrm{R}$ at all. Sanyal18 Li18 |
| Random-indicator gadget total | \(\Theta(n)\) | Squeeze: $\mathrm{R}=\Omega(\mathrm{fbs})=\Omega(n)$ and $\mathrm{R}\le\mathrm{D}=n$. Nothing about this gadget is easy for randomness; the point of it is the shape of the $0$-side, not a speed-up. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{R}=\Omega(\mathrm{fbs})$. The gap up to $\mathrm{D}=\widetilde\Theta(n)$ is not closed here -- closing it in the other direction is precisely what \(f_{\mathrm{GJPW}}\) was built for. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Theta(n^{2/3})\) | Lower bound $\widetilde\Omega(k^2)=\widetilde\Omega(n^{2/3})$: [GJPW18, Lem. 8] proves it even against the weaker one-sided-approximate model, $\mathrm{coWAPP}^{dt}_{0.05}(\mathrm{TL})\ge\widetilde\Omega(\mathrm{UP}^{dt}(\mathrm{TL})^2)$. Upper bound from $\mathrm{R}\le\mathrm{D}=\widetilde O(n^{2/3})$. GJPW18 |
| Ambainis' exact-quantum function total | \(3^d\) | The all-zero input has full sensitivity, so $\mathrm{R}=\Omega(\mathrm{s})=\Omega(3^d)$; and $\mathrm{R}\le\mathrm{D}=3^d$. So the exact quantum speedup below is a speedup over bounded-error randomized query complexity too. Ambainis13 |
| FORRELATION partial | \(\widetilde\Theta(\sqrt n)\) | Lower bound $\Omega(\sqrt n/\log n)$ [AaronsonAmbainis18], improved to $\widetilde\Omega(\sqrt n)$ via Fourier growth of decision trees [Tal20]. Matching $O(\sqrt n)$ upper bound. AaronsonAmbainis18 Tal20 |
| k-FORRELATION partial | \(\widetilde\Theta\!\big(n^{1-1/k}\big)\) | Lower bound proved independently by [BansalSinha21] and [SSW21]; matches the Aaronson-Ambainis upper bound $\mathrm{R}=O(n^{1-1/(2\mathrm{Q})})$. BansalSinha21 SSW21 |
| Simon's problem partial | \(\Theta(2^{n/2})\) | Simon97 |
| Deutsch-Jozsa partial | \(O(1)\) | Two random samples suffice with bounded error -- so this is an exact-quantum-vs-deterministic separation only. |
| Bernstein-Vazirani partial | \(\Theta(n)\) | Recovering $s$ needs $n$ bits of information from one-bit answers, so $\mathrm{R} = \Omega(n)$ even with bounded error; and $\mathrm{R} \le \mathrm{D} = n$. |
| Unique search partial | \(\Theta(n)\) | Against $0^n$ versus a uniformly random $e_i$, $q$ queries see all-zero answers with probability $1 - q/n$, so $q = \Omega(n)$. The canonical quadratic quantum speed-up sits on top of this. |
| Two-or-none search partial | \(\Theta(n)\) putative | Against $0^n$ versus a uniformly random pair, $q$ queries miss both planted ones with probability $\binom{n-q}{2}/\binom n2 \ge (1 - q/n)^2$, so $q = \Omega(n)$; and $\mathrm{R} \le \mathrm{D} = n-1$. |
| Marked bit partial | \(\Theta(n)\) putative | Plant one mark at a uniformly random cell with a uniformly random colour. All-zero answers are what the algorithm sees unless it queries a bit of the marked cell, and each cell contributes only the bit it did not query: after $t$ queries the posterior still gives weight $\Omega((n-t)/n)$ to the other colour, so $t = \Omega(n)$. Upper: $\mathrm{R} \le \mathrm{D} = n$. |
| Dense marked bit partial | \(\Theta(1)\) | At most $\mathrm{R}_0 = \Theta(1)$, and at least $1$. |
| Unstructured search (relation) relation | \(\Theta(n)\) | |
| FIND-1 under a density promise relation | \(O(1)\) | |
| Approximate Hamming weight relation | \(\Theta(1)\) | At constant $\varepsilon$; the honest dependence is $\Theta(1/\varepsilon^2)$ samples for an $\varepsilon n$-accurate estimate. |
| Correlated-string search relation | \(\Theta(\sqrt n)\) | Query a uniformly random set $S$ of $c\sqrt n$ coordinates, copy $x$ on $S$ and flip fair coins elsewhere: the distance is $\mathrm{Bin}(n-|S|,1/2) \approx n/2 - c\sqrt n/2$ with deviation $O(\sqrt n)$, so a large enough constant $c$ works. The matching $\Omega(\sqrt n)$ is [GLSS19]. GLSS19 |
| SearchCNF relation | \(\Theta(1)\)· | For a random $\Delta$-dense unsatisfiable $k$-CNF with $\Delta$ a large enough constant: with high probability every assignment falsifies a constant fraction of the clauses, so sampling $O(1)$ clauses at random and reading their $k$ variables finds a falsified one. At least one query is needed, so $\Theta(1)$. |
| Gap-Majority partial | \(\Theta(\min(n, 1/\delta^2))\) | Sample $\Theta(1/\delta^2)$ coordinates and compare the empirical density with $1/2$; the lower bound is the standard bias-amplification argument (Lemma 26 of [BenDavidBlais20composition] for the $\delta = 2/\sqrt{n}$ instance, where it reads $\mathrm{R} = \Theta(n)$). BenDavidBlais20composition |
| Gap-Majority at constant gap partial | \(\Theta(1)\) | Sample $O(1)$ coordinates and take the empirical majority; $\Theta(1/\delta^2)$ at $\delta = 1/4$. Against $\mathrm{D} = \Theta(n)$ this is the standard proof that $\mathrm{D}$ is unbounded in terms of $\mathrm{R}$ on partial functions. BenDavidBlais20composition |
| Parity-labelled FIND-1 partial | \(\Theta(1)\) | $\mathrm{R} \le \mathrm{R}_0 = O(1)$, and at least one query. |
| Approximate index partial | \(\Theta(\sqrt{k\log k}) = \Theta(\sqrt{\log n\,\log\log n})\) | Lemma 27. Upper: read the first $8\sqrt{k\log k}$ bits of $a$, fill the rest of $b$ with fair coins, query $x_b$. Lower: an algorithm making $\sqrt{k\log k}$ queries can be assumed never to query the array (pretend the answer is $2$), and then it must still name a small set of candidate addresses one of which lands in the ball -- i.e. guess $k/2 + \sqrt{k\log k}$ of the unread bits of a uniformly random string correctly, which Chernoff forbids. BenDavidBlais20composition |
| Collision problem partial | \(\Theta(\sqrt n)\) | Birthday paradox both ways. |
| Element distinctness total | \(\Theta(n)\) | |
| Ambainis-Belovs function partial | \(\Omega(n^{1/3})\) | Sandwiched: $\mathrm{Q} \le \mathrm{R} \le \mathrm{D}$, i.e. between $\Omega(n^{1/3})$ and $O(n)$. The paper says nothing more about the classical side. |
| Ben-David-Kundu total search problems relation | \(\widetilde\Omega(\sqrt n)\) | At least $\mathrm{Q} = \widetilde\Omega(\sqrt n)$; no better classical lower bound is claimed, and the trivial ceiling is the input length $t n^2\log(n/2)$. |
| Yamakawa-Zhandry problem relation | \(2^{\Omega(n)}\) | YamakawaZhandry22 |
| Surjectivity total | \(\Theta(n)\) | Sandwiched: $\mathrm{bs}(f) \le 3\,\mathrm{R}(f) \le 3n$, and $\mathrm{bs} = \Theta(n)$ here. (The $\mathrm{Q} \le \mathrm{R}$ route would only give $\tilde\Theta(n)$; block sensitivity removes the log.) |
| $k$-distinctness total | \(\Theta(n)\) | Read everything; the lower bound is the usual hybrid argument in the element-query model. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | [CGP26, Lem. 3.3(3)] proves $\mathrm{R} = \Theta(m^2)$ for every subgraph-containment problem whose pattern keeps an edge after pinning, by embedding classical search over the $\binom m2$ pairs. Often asserted without citation, e.g. [LeGall14, §1]. CGP26 |
| Recursive Fourier sampling partial | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | [BernsteinVazirani97, Thm. 8.4.6 / Cor. 8.4.7]: relative to a random legal oracle, with probability $1$, the language is not in $\mathrm{BPTime}(T(n))$ for any $T(n) = n^{o(\log n)}$; the explicit bound is $\tfrac1{12}\varphi(n/4)$ with $\varphi(n) = n(n/2)\cdots 1 > n^{(\log n)/2}$. So the separation is superpolynomial, not exponential. The often-quoted $\Theta(n^\ell)$ for general $\ell$ is a folklore extrapolation -- BV prove only the $\ell = \log n$ case. BernsteinVazirani97 |
| Welded trees relation | \(\tilde\Theta(2^{n/2})\)· | The window is $[\Omega(2^{n/2}/n),\ O(n\,2^{n/2})]$, so the exponent is pinned and only the polynomial factor is open. Lower: [Liu17thesis, Cor. 25], for the easier task of finding either the EXIT or any cycle; [AaronsonAmbainis18, fn. 5] asserts $\Omega(\sqrt N)$ for constant success probability. Refereed but weaker: $\Omega(2^{n/6})$ [CCDFGS03, Thm. 9] and $\Omega(2^{n/3})$ [FennerZhang03, Thm. 1.2], both in the exponentially-small-success regime. Upper: from $\mathrm{R} \le \mathrm{D}$. Medium confidence: the strong lower bound lives in a thesis and a footnote. Liu17thesis AaronsonAmbainis18 |
| Local search on the hypercube relation | \(\Theta(2^{n/2}\sqrt n)\) | Upper: Aldous' generic $O(\sqrt{N\Delta})$ with $N = 2^n$, $\Delta = n$. Lower: [Zhang09localsearch, Thm. 2], after [Aldous83] ($2^{n/2-o(n)}$) and [Aaronson06, Thm. 15] ($\Omega(2^{n/2}/n^2)$). Zhang09localsearch Aldous83 |
| Local search on the grid relation | \(\Theta(k^{d/2})\ (d \ge 4)\) | [Zhang09localsearch, Thm. 3], matching Aldous' $O(\sqrt{N\Delta}) = O(k^{d/2})$. The two small dimensions cost a log: $\mathrm{R} = \tilde\Theta(k^{3/2})$ at $d = 3$, from $\Omega((k^3/\log k)^{1/2})$ [Zhang09localsearch, Thm. 3]; and $\mathrm{R} = \tilde\Theta(k)$ at $d = 2$, from $\Omega(k^{1-\delta})$ for every constant $\delta > 0$ [SunYao09] via Sarkozy-Szemeredi, against Aldous' $O(k)$ -- [Zhang09localsearch] had reached only $\Omega(k^{2/3})$ there. Zhang09localsearch Aldous83 SunYao09 |
| Fourier fishing relation | \(\Omega(N/\log N)\) | [AaronsonChen17, Thm. 6.4]: no $o(N/\log N)$-query randomized algorithm solves promise-fishing with probability $\mathrm{Succ}_R + \Omega(1)$. Note this is the relation; [AaronsonAmbainis18, Thm. 27] proves the analogous bound for the sampling problem and leaves the relation as a "plausible conjecture", which is what Aaronson-Chen discharge. AaronsonChen17 |
| Ordered search partial | \(\log_2 n - \Theta(1)\) | Randomness buys a constant number of queries, not a constant factor. Upper: $\mathrm{R}\le\mathrm{D}$. Lower, by Yao plus leaf-counting: under the uniform distribution on the $n+1$ inputs a $T$-query deterministic tree is right on at most $2^T$ of them, so success $\ge 2/3$ forces $T \ge \log_2(n+1) - \log_2(3/2)$. |
| Tseitin search on an expander relation | \(\Theta(n)\) putative | Lower: $\mathrm{R} = \Omega(\mathrm{cbs}) = \Omega(n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Upper: read every edge. Sampling -- the trick that makes \(\mathrm{Search}(\varphi)\) easy -- fails here, because an adversarial input can leave exactly one vertex violated. GoosPitassi14 |
| Inner product mod 2 total | \(\Theta(n)\) | Sandwiched: $\mathrm{bs} \le 3\mathrm{R}$ (indeed $\mathrm{R} = \Omega(\mathrm{s})$) and $\mathrm{R} \le \mathrm{D} = n$. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^3) = \Theta(N)\) | Randomised evaluation of a depth-two AND-OR tree with fan-ins $m$ and $m^2$ costs $\Theta(m\cdot m^2)$. SaksWigderson86 Snir85 |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: $\mathrm{bs}/3 \le \mathrm{R} \le \mathrm{D}$, with $\mathrm{bs} = \Theta(m)$ and $\mathrm{D} = O(m)$. |
| Scorpion graphs total | \(\Theta(m)\) | Between $\Omega(\sqrt{\mathrm{bs}})$ and $\mathrm{D} = O(m)$; nothing below $\Theta(m)$ is possible because the property depends on every vertex. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | Upper: $\mathrm{R} \le \mathrm{D}$. Lower: $\Omega(m^2)$ -- take a random graph on the threshold and note that a spanning-tree/isolated-vertex distinction survives $o(m^2)$ random probes. So connectivity is one of the (few) monotone graph properties where randomized AKR is known. |
| Ben-David–Kothari championship function total | \(O(n\log n)\) | Lemma 3; the logarithm pays for binary labels. BenDavidKothari26 |
| Ambainis–Iraids–Kokainis unambiguous DNF total | \(\Theta(n)\) | Theorem 2.2 and the universal C = O(R²) bound. AIK26 |
| Meiburg’s parity-pointer family total | \(\Theta(q^3\log^2 q)\) | Meiburg26composition |
| Meiburg’s majority-pointer family total | \(\Theta(q^3\log^2 q)\) | Meiburg26composition |
| Meiburg’s parity-masked majority family total | \(\Theta(q^3\log^2q)\) | Meiburg26composition |
| Meiburg’s total noisy-query separation total | \(\Omega(q^{11}\log q)\) | Theorem 4.1: substitute u_q=Θ(q^4) and ℓ_q=Θ(log q) in its lower bound. Meiburg26composition |
| Meiburg’s maximal composition-rate separation total | \(\Theta(q^5\log q)\) | Meiburg26composition |
| OpenAI’s nearly quartic randomized–quantum family total | \(\Omega(m^{2-1/k}/\log^2m)\) | Theorem 1.1, for each fixed k≥2. OpenAI26QuarticRQ |
| Complement of the Ambainis–Iraids–Kokainis DNF total | \(\Theta(n)\) | Bounded-error randomized complexity is invariant under output complementation. AIK26 |