Robust quantum query complexity
Quantum queries when the oracle is noisy (each query answer is corrupted).
Definition
The quantum analogue of the \(\mathrm{N}_{p}(f)\) model: the oracle returns a corrupted bit, or more precisely the algorithm has access to a "noisy" version of $x$ and must be robust to it. Buhrman-Newman-Röhrig-de Wolf showed that $n$ noisy quantum queries suffice to recover all $n$ bits with high probability.
Parameters
\(p\) (p) default \(constant\)
Basic facts
- $\mathrm{Q}^{\mathrm{rob}}(\mathrm{PARITY}_n) = \Theta(n)$ -- no $\log n$ overhead, in contrast to the classical $\Theta(n\log n)$ [FRPU94 vs BNRdW05].
- $\mathrm{Q}^{\mathrm{rob}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ in general; whether the log is needed is open.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Q}^{\mathrm{rob}}(f)\). “\(\mathrm{Q}^{\mathrm{rob}}(f)\) in terms of it” is the pair with \(\mathrm{Q}^{\mathrm{rob}}(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 3 above are this entry’s hand-picked neighbours; the other 90 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(\sqrt n)\) | Robust Grover: search over bounded-error inputs costs $O(\sqrt n)$ with no log factor, by amplitude amplification around a subroutine whose error is never amplified. Classically, noisy OR costs $\Theta(n)$ either way, so the quantum speedup survives noise intact. HoyerMoscadeWolf03 BNRdW05 |
| AND total | \(\Theta(\sqrt n)\) | Robust Grover search for a zero costs $O(\sqrt n)$ with no log factor, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt n)$. The \(\mathrm{OR}_n\) entry after negating the input bits. HoyerMoscadeWolf03 BNRdW05 |
| PARITY total | \(\Theta(n)\) | The headline robustness result: $n$ noisy quantum queries recover all $n$ bits, so $\mathrm{Q}^{\mathrm{rob}} = O(n)$, matching $\mathrm{Q} = n/2$ up to a constant. Classically the same task costs $\Theta(n\log n)$ [FRPU94] -- noise imposes a logarithmic tax on randomized algorithms that quantum algorithms simply do not pay. An explicit degree-$O(n)$ robust polynomial was later given by [Sherstov13robust]. BNRdW05 FRPU94 |
| MAJORITY total | \(\Theta(n)\) | Sandwiched between $\mathrm{Q} = \Theta(n)$ and the universal $O(n)$ upper bound. BNRdW05 |
| Threshold total | \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) | Theorem 4 of [BNRdW05] gives a robust quantum algorithm using $O(\sqrt{n(n-\Gamma(f)+1)})$ queries for every symmetric $f$; here $\Gamma = |2k-n-1|$, so $n - \Gamma + 1$ is $2k$ for $k \le (n+1)/2$ and $2(n-k+1)$ otherwise, and the bound reads $O(\sqrt{k(n-k+1)})$. That matches $\mathrm{Q}$ from above, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$. So noise is free for the quantum algorithm at every $k$, while classically it costs a $\log$ factor at $k \approx n/2$. BNRdW05 |
| Symmetric functions (general) total | \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) | Same as the recorded $\mathrm{Q}$, since $n - \Gamma(f) \ge 1$ for non-constant $f$. Theorem 4 of [BNRdW05]: for every symmetric $f$ there is a robust quantum algorithm using $O(\sqrt{n(n-\Gamma(f)+1)})$ queries -- robust counting suffices, since $f$ is constant on the middle band of weights of width $\Gamma(f)$. The matching lower bound is $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt{n(n-\Gamma(f))})$ by Paturi (the \(\mathrm{Q}_{\varepsilon}(f)\) line). So the whole symmetric family tolerates noisy inputs for free, in contrast with the classical $\log$ tax at \(\oplus_n\) and \(\mathrm{MAJ}_n\). BNRdW05 |
| EXACT-HALF total | \(\Theta(n)\) | Sandwiched between $\mathrm{Q} = \Theta(n)$ and the universal $O(n)$ robust upper bound. BNRdW05 |
| ODD-MAX-BIT total | \(\Omega(\sqrt n),\ O(n)\) | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt n)$. Upper: the universal $O(n)$ bound of [BNRdW05] for recovering all $n$ noisy bits. Whether the $\sqrt n$ algorithm survives noise is the interesting question and is not settled here. BNRdW05 |
| ADDRESS / multiplexer total | \(\Omega(k),\ O(k\log k)\) | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(k)$. Upper: read the address and the entry classically, repeating each query $O(\log k)$ times. The universal $O(\mathrm{arity})$ bound of [BNRdW05] is useless here, the arity being $k+2^k$. BNRdW05 |
| Binary tree navigation total | \(\Omega(k),\ O(k\log k)\) | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(k)$. Upper: run the depth-$k$ walk classically, repeating each query $O(\log k)$ times. The universal $O(\mathrm{arity})$ bound of [BNRdW05] is useless here, since the arity is $2^k-1$; whether the $\log k$ can be removed is exactly the open case of robust computation for very shallow, very wide functions. BNRdW05 |
| TRIBES total | \(\Theta(\sqrt n)\)· putative | At least $\mathrm{Q} = \Omega(\sqrt n)$. The matching upper bound is the ordinary $\sqrt s \cdot \sqrt w$ algorithm with both Grover layers replaced by robust amplitude amplification, which tolerates bounded-error inputs with no log overhead. So the quantum speedup over $\mathrm{R} = \Theta(n)$ survives noisy oracles intact. HoyerMoscadeWolf03 BNRdW05 |
| AND-OR tree (depth 2) total | \(\Theta(n) = \Theta(\sqrt N)\)· | Lower bound $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n)$. Upper bound: Grover search on bounded-error inputs costs $O(\sqrt m)$ calls with no logarithmic overhead [HoyerMoscadeWolf03], and noisy oracle access to a block can be turned into bounded-error access at constant amortised cost [BNRdW05]. Run robust search inside each $\mathrm{OR}_n$ block ($O(\sqrt n)$ noisy queries) and robust search again at the outer $\mathrm{AND}_n$ over the $n$ bounded-error block answers ($O(\sqrt n)$ calls): $O(n)$ in total. HoyerMoscadeWolf03 BNRdW05 |
| NAND tree (balanced AND-OR formula) total | \(\Omega(\sqrt N),\ O(\sqrt N\log N)\) | $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt N)$, and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ in general [BNRdW05]. Whether the logarithm can be removed for the NAND tree is open; it can be for \(\oplus_n\). BNRdW05 |
| Recursive MAJORITY-of-3 total | \(\Omega(2^{\,d}),\ O(d\,2^{\,d})\) | $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(2^d)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. Unlike the classical side, the quantum value is pinned to within the logarithm because $\mathrm{Q} = \Theta(2^d)$ is exact [Reichardt11]. BNRdW05 |
| Kushilevitz's function (iterated) total | \(\Omega(\sqrt N),\ O(N)\) | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt N)$. Upper: $N$ noisy quantum queries recover the whole input with high probability [BNRdW05], so $\mathrm{Q}^{\mathrm{rob}} = O(N)$ for any function; this beats $O(\mathrm{Q}\log \mathrm{Q})$ because $\mathrm{Q}$ itself is only known up to an $N^{0.11}$ window here. BNRdW05 |
| Rubinstein's function total | \(\Omega(\sqrt N),\ O(\sqrt N\log N)\) | $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt N)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. BNRdW05 |
| Ambainis-Sun function total | \(\Omega(\sqrt N),\ O(N^{3/4}\log N)\) | $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt N)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05], with the recorded $\mathrm{Q} = O(N^{3/4})$. The window is inherited wholesale from the open $\mathrm{Q}$ window. BNRdW05 |
| AND composed with NOT-EXACT-HALF total | \(\Omega(n^{3/2}),\ O(n^{3/2}\log n)\) | $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n^{3/2})$, and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. The generic $O(N) = O(n^2)$ bound of [BNRdW05] is weaker. BNRdW05 |
| Meiburg's tournament-subcube function total | \(\Omega(118.3^{\,d})\) putative | A robust quantum algorithm works in particular with a clean oracle, so $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(118.3^{\,d})$. The generic upper bound $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05] is vacuous here, since no upper bound on $\mathrm{Q}$ is known. BNRdW05 |
| Pointer functions total | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$: $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05] applied to $\mathrm{Q}=\widetilde O(n^{1/4})$. BNRdW05 |
| Cheat-sheet functions total | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05] with $\mathrm{Q}=\widetilde\Theta(n)$. BNRdW05 |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}=\widetilde\Omega(n^3)$ [BNRdW05]. BNRdW05 |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{2/3}),\ \widetilde O(n^2)\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range. BNRdW05 |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}=\Omega(\sqrt n)$ [BNRdW05]. BNRdW05 |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range $[\widetilde\Omega(n^{1/4}),\widetilde O(n)]$. BNRdW05 |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/6}),\ \widetilde O(n^{2/3})\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range. BNRdW05 |
| Ambainis' exact-quantum function total | \(\widetilde\Theta(2.1213^d)\) | Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}$ and $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], with $\mathrm{Q}=\Theta(2.1213^d)$. BNRdW05 |
| FORRELATION partial | \(\Theta(1)\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$, and $\mathrm{Q} = 1$. So even an oracle whose every answer is only a bounded-error bit is beaten by $O(1)$ quantum queries, against $\mathrm{R} = \widetilde\Theta(\sqrt n)$ and $\mathrm{N}_p = \widetilde\Theta(\sqrt n)$ classically. |
| k-FORRELATION partial | \(O(k\log k)\) | The generic robustification bound $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$ applied to $\mathrm{Q} = \lceil k/2\rceil$; and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$. Still independent of $n$. |
| Simon's problem partial | \(\widetilde\Theta(n)\) | Between $\mathrm{Q} = \Theta(n)$ and $\mathrm{Q}\log\mathrm{Q} = O(n\log n)$. So the exponential separation survives a noisy oracle. |
| Deutsch-Jozsa partial | \(\Theta(1)\) | At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = 1$. |
| Bernstein-Vazirani partial | \(\Theta(1)\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ with $\mathrm{Q} = 1$, so a robust oracle costs only a constant here. |
| Unstructured search (relation) relation | \(\Theta(\sqrt n)\)· | Grover search is robust: $O(\sqrt n)$ queries still suffice when each oracle answer is only a bounded-error bit, so the $\log$ in $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$ is not needed here; and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$. |
| FIND-1 under a density promise relation | \(\Theta(1)\) | At most $\mathrm{N}_p = \Theta(1)$ (a noisy quantum algorithm can simulate the classical one), and at least $\mathrm{Q} = \Theta(1)$. |
| Approximate Hamming weight relation | \(\Theta(1)\) | At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = \Theta(1)$. |
| SearchCNF relation | \(\Theta(1)\) | At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = \Theta(1)$. |
| Gap-Majority partial | \(\widetilde\Theta(\min(n, 1/\delta))\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$. |
| Gap-Majority at constant gap partial | \(\Theta(1)\) | Between $\mathrm{Q}$ and $O(\mathrm{Q}\log\mathrm{Q})$. |
| Parity-labelled FIND-1 partial | \(\Theta(1)\) | Between $\mathrm{Q} = \Theta(1)$ and $\mathrm{N}_p = \Theta(1)$. |
| Approximate index partial | \(\widetilde O(\sqrt{k\log k})\) | $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ with $\mathrm{Q} = O(\sqrt{k\log k})$. |
| Collision problem partial | \(\widetilde\Theta(n^{1/3})\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$. |
| Element distinctness total | \(\widetilde\Theta(n^{2/3})\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$, with $\mathrm{Q} = \Theta(n^{2/3})$. A noisy oracle costs at most a log factor. |
| Ambainis-Belovs function partial | \(\Omega(n^{1/3})\) | Robust queries are at least as expensive as exact ones: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(n^{1/3})$. |
| Ben-David-Kundu total search problems relation | \(\widetilde\Omega(\sqrt n)\) | At least $\mathrm{Q}$: noisy oracles cannot be cheaper than exact ones. |
| Yamakawa-Zhandry problem relation | \(\mathrm{poly}(n)\) | At most $\mathrm{Q}\log\mathrm{Q} = \mathrm{poly}(n)$ by generic robustification, at least $\mathrm{Q}$. So even a noisy quantum oracle keeps the exponential advantage. |
| Surjectivity total | \(\tilde\Theta(n)\) | Between $\mathrm{Q} = \tilde\Theta(n)$ and the universal ceiling $\mathrm{Q}^{\mathrm{rob}} \le O(n)$ of Buhrman-Newman-Röhrig-de Wolf, who recover all $n$ bits from $O(n)$ noisy queries. Noise is free here because the problem is already maximally hard. |
| $k$-distinctness total | \(\tilde\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) | Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/4-1/(4(2^k-1))})$ by the row above. Even the fourteen-year-old exponent is noise-robust up to a log. |
| Triangle finding total | \(\Omega(m),\ O(m^{5/4}\log m)\) | Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so the window is the $\mathrm{Q}$ window plus a log. Noise is not where the difficulty lies. |
| Recursive Fourier sampling partial | \(\Omega(2^{\ell}),\ O(\ell\,2^{\ell})\) | Sandwiched by the generic $\mathrm{Q}(f) \le \mathrm{Q}^{\mathrm{rob}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) around $\mathrm{Q} = \Theta(2^{\ell})$ at $g = g_{\mathrm{mod}3}$. Whether the $\ell$ is needed is open: the Bernstein-Vazirani kickback is exact and has no error to amplify, but the recursion must re-run it $\ell$ levels deep. |
| Welded trees relation | \(\Omega(n),\ O(n\log n)\) | Squeezed by $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) around $\mathrm{Q} = \Theta(n)$. So the exponential separation from $\mathrm{R}$ survives noisy oracles intact -- unusually, since the quantum walk's advantage is an interference effect. |
| Local search on the hypercube relation | \(\tilde\Theta(2^{n/3})\) | Between $\mathrm{Q} = \Theta(2^{n/3}n^{1/6})$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(2^{n/3}n^{7/6})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). |
| Local search on the grid relation | \(\tilde\Theta(k^{d/3})\ (d \ge 6)\) | Between $\mathrm{Q} = \Theta(k^{d/3})$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(k^{d/3}\log k)$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). |
| Fourier fishing relation | \(\Theta(1)\)· | Still constant: $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) reads $O(1)$ at $\mathrm{Q} = 1$, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = 1$. So the largest known relational speedup is not an artefact of a noiseless oracle. Medium confidence because the generic simulation is stated asymptotically and the constant-$\mathrm{Q}$ case needs the $O(\mathrm{Q})$ form of it. |
| Ordered search partial | \(\tilde\Theta(\log n)\) | Between $\mathrm{Q} = \Theta(\log n)$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(\log n\log\log n)$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). |
| Tseitin search on an expander relation | \(O(\sqrt n\log n)\) | $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) with $\mathrm{Q}=O(\sqrt n)$. |
| Inner product mod 2 total | \(\Theta(n)\) | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n)$. Upper: $n$ noisy quantum queries recover all $n$ input bits with high probability [BNRdW05], so no function on $n$ bits costs more. Unlike the classical $\mathrm{N}_p = \Theta(n\log n)$ above, there is no $\log$ -- the same quantum-vs-classical noise gap as for \(\oplus_n\). BNRdW05 |
| Minsky-Papert one-in-a-box total | \(\Theta(m^{3/2}) = \Theta(\sqrt N)\)· | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(m^{3/2})$. Upper: the $O(\sqrt N)$ algorithm for a two-level AND-OR tree is robust quantum search [HoyerMoscadeWolf03] -- that is exactly the point of the technique -- so noise costs only a constant factor and no $\log$. HoyerMoscadeWolf03 |
| Sink of a tournament total | \(\Omega(\sqrt m),\ O(m\log m)\) | Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$, and $\mathrm{Q}$ is itself open here; the upper end also follows from $\mathrm{Q}^{\mathrm{rob}} \le \mathrm{N}_p = O(m\log m)$. |
| Scorpion graphs total | \(\Omega(\sqrt m),\ O(m\log m)\) | Lower: $\mathrm{Q} \le \widetilde{\mathrm{Q}}$ and $\mathrm{Q} \ge \widetilde{\deg}/2 = \Omega(\sqrt m)$. Upper: $\widetilde{\mathrm{Q}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ with $\mathrm{Q} = O(m)$. Inherits the whole $\widetilde{\deg}$-vs-$\deg$ gap of \(\widetilde{\deg}_{\varepsilon}(f)\). |
| Graph connectivity total | \(\Omega(m^{3/2}),\ O(m^{3/2}\log m)\) | Generic: $\mathrm{Q}(f) \le \widetilde{\mathrm{Q}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$, with $\mathrm{Q} = \Theta(m^{3/2})$. |