Q The Query Complexity Zoo
\(\mathrm{RS}(f)\)

Sabotage complexity

Randomized cost of finding a "sabotaged" (damaged) input bit; the first measure with perfect composition.

Definition

Define the sabotaged problem $f_{\mathrm{sab}}$: the input is a partial assignment with some coordinates set to $\ast$ such that the $\ast$'s genuinely matter (the value of $f$ is not determined), and the goal is to find one $\ast$. $\mathrm{RS}(f)$ is the bounded-error randomized query complexity of $f_{\mathrm{sab}}$.

Basic facts

  • Formally $\mathrm{RS}(f) := \mathrm{R}_0(f_{\mathrm{sab}})$; using $\mathrm{R}$ instead of $\mathrm{R}_0$ changes nothing up to constants [BenDavidKothari18, Def. 10].
  • $\mathrm{RS}(f\circ g) \ge \mathrm{RS}(f)\,\mathrm{RS}(g)$ -- perfect composition [BenDavidKothari18, Thm 19].
  • $\mathrm{R}(f\circ g^n) = \Omega(\mathrm{R}(f)\,\mathrm{RS}(g))$ [BenDavidKothari18, Thm 21].
  • $\mathrm{R}_\varepsilon(f) \ge \bar{\mathrm{R}}_\varepsilon(f) \ge (1-2\varepsilon)\,\mathrm{RS}(f)$ [BenDavidKothari18, Thm 12].
  • Quadratically tight for total $f$: $\mathrm{R}(f) = O(\mathrm{RS}(f)^2\log \mathrm{RS}(f))$ [BenDavidKothari18, Thm 32].
  • $\mathrm{RS}$ can be quadratically larger than the partition bound, and $\mathrm{RS}(f) = \tilde\Omega(\mathrm{Q}(f)^{2.5})$ for some total $f$ [BenDavidKothari18, Thm 30].
  • $\mathrm{RS}(g) = \tilde\Omega(\mathrm{D}^{\mathrm{prod}}(g))$ for total $g$, and the gap is polynomial (NAND-tree) [Sanyal24].
  • The quadratic tightness above is total-only, and badly so. On partial functions $\mathrm{R}$ is unbounded in terms of $\mathrm{RS}$: any promise whose two sides are far apart in Hamming distance has $\mathrm{RS} = O(1)$ whatever its randomized complexity, because every sabotaged input is then riddled with stars. The collision problem is the clean instance -- $\mathrm{RS}(\mathrm{COL}_n) = \Theta(1)$ against $\mathrm{R} = \Theta(\sqrt n)$ [BenDavidKothari18, Sec. 1.4]. See \(\mathrm{COL}_n\).
  • $\bar{\chi}(g) = \Omega(\mathrm{RS}(g))$ for all partial $g$ [GLSS19, Thm 7]; the same collision witness makes that gap unbounded. Repairing the partial-function collapse is what $\chi$, $\bar\chi$ and $\mathrm{LR}$ are for: each is $\Omega(\sqrt{\mathrm{R}})$ even off the promise, and $\mathrm{RS}$ is not.
  • Total functions now separate sabotage and randomized complexity by $\Omega(\log N)$ [Meiburg26composition]; \(P_q\) is a witness. Conflict and sabotage are incomparable on total functions: the opposite directions use that family and \(\mathrm{AND}_n \circ \mathrm{OR}_n\).

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{RS}(f)\). “\(\mathrm{RS}(f)\) in terms of it” is the pair with \(\mathrm{RS}(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{RS}(f)\) in terms of it It in terms of \(\mathrm{RS}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 derived open pair → total1,2 partial∞ open pair →
\(\bar{\chi}(f)\) Max-conflict complexity total1,1 partial1,1 open pair → total1,2 partial∞ open pair →
\(\chi(f)\) Conflict complexity total1,2 partial1,? open pair → total1,2 partial1,? open pair →
\(\mathrm{LR}(f)\) Linearised randomized complexity total1,1 partial1,1 derived open pair → total1,2 partial∞ derived open pair →
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity total1,? partial∞ derived open pair → total1,1 partial1,? open pair →
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity total1,3 partial1,? derived open pair → total1,2 partial1,? derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\) At most $\mathrm{R}=\Theta(n)$. For the lower bound, take the sabotaged input with a single $\ast$ and zeros elsewhere: the value is undetermined, and finding the $\ast$ among $n$ positions needs $\Omega(n)$ queries. BenDavidKothari18
AND total \(\Theta(n)\) At most $\mathrm{R} = \Theta(n)$. For the lower bound take the sabotaged input with a single $\ast$ and ones elsewhere: the value is undetermined, and finding the $\ast$ among $n$ positions needs $\Omega(n)$ queries. BenDavidKothari18
PARITY total \(\Theta(n)\) At most $\mathrm{R}=n$; and a sabotaged input with a single $\ast$ hides it among $n$ positions. BenDavidKothari18
MAJORITY total \(\Theta(n)\) At most $\mathrm{R}=\Theta(n)$; and the sabotaged input with $(n-1)/2$ ones, $(n-1)/2$ zeros and a single $\ast$ hides that $\ast$ among $n$ positions. BenDavidKothari18
Threshold total \(\Theta(n)\) Squeezed: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$. BenDavidKothari18
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. So every symmetric function composes perfectly on the inside. BenDavidKothari18
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BenDavidKothari18
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BenDavidKothari18
ADDRESS / multiplexer total \(\Theta(k)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BenDavidKothari18
Binary tree navigation total \(\Theta(k)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BenDavidKothari18
TRIBES total \(\Theta(n)\) putative At most $\mathrm{R} = \Theta(n)$. For the lower bound take the sabotaged input in which every tribe has exactly one $0$ except one distinguished tribe, which is all $1$s apart from a single $\ast$; the value is undetermined. Ruling out a tribe means finding its unique $0$, which costs $\Omega(w)$ queries, and a constant fraction of the $s$ tribes must be ruled out, so $\Omega(sw) = \Omega(n)$. BenDavidKothari18
AND-OR tree (depth 2) total \(\Theta(n^2)\) Theorem 9.1; for LR use max-conflict ≤ O(LR) ≤ O(R). The conflict bound is the theorem’s bracket, not the stronger introduction-table upper bound. Meiburg26composition
NAND tree (balanced AND-OR formula) total \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) putative Not pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(\sqrt N)$ -- star out a uniformly random one of the $\mathrm{bs}$ disjoint sensitive blocks of a maximally block-sensitive input; every unstarred bit agrees with that input, so finding a $\ast$ is unstructured search over the blocks.
Recursive MAJORITY-of-3 total \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) putative Not pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(2^d)$ -- star out a uniformly random one of the $\mathrm{bs}$ disjoint sensitive blocks of a maximally block-sensitive input; all other bits agree with it, so finding a $\ast$ is unstructured search over the blocks. Sabotage complexity composes perfectly, so pinning $\mathrm{RS}$ here would immediately pin the \(\mathrm{R}^{*}(f)\) exponent.
Kushilevitz's function (iterated) total \(\Theta(N)\) putative Pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(N)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(N)$ -- at the fully sensitive input, star out one uniformly random coordinate; every other bit agrees with that input, so finding the $\ast$ is unstructured search over all $N$ positions.
Rubinstein's function total \(\Theta(N)\) putative Pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(N)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(N)$ -- at $0^N$, star out a uniformly random one of the $N/2$ disjoint adjacent pairs; every unstarred bit is $0$ as usual, so finding a $\ast$ is unstructured search over the $N/2$ pairs.
Ambainis-Sun function total \(\Theta(N)\) putative Pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(N)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(N)$ -- at $0^N$, star out a uniformly random one of the $(3k+2)(2k+1)$ disjoint sensitive blocks; every unstarred bit is $0$ as usual, so finding a $\ast$ is unstructured search over those blocks.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) putative Pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(n^2)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(n^2)$ -- take a $1$-input with every block at weight $n/2+1$ and star out a uniformly random one of the $n(n/2+1)$ disjoint sensitive blocks; all remaining bits look as usual, so finding a $\ast$ is unstructured search.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative $\mathrm{RS} = \Omega(\mathrm{bs})$: at a maximally block-sensitive input, star out a uniformly random one of the disjoint sensitive blocks; every unstarred bit agrees with that input, so finding a $\ast$ is unstructured search over the blocks. No upper bound is available, since only a lower bound on $\mathrm{R}$ is known here.
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$. Ceiling: $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{RS}=O(\mathrm{R})=\widetilde O(\sqrt n)$. Floor: $\mathrm{fbs}\le\mathrm{CG}^{\mathrm{pub}}\le\mathrm{RS}$, and $\mathrm{fbs}=\widetilde\Theta(\sqrt n)$ here. So randomized sabotage is tight against $\mathrm{R}$ on this family, consistent with the fact that no total function with $\mathrm{RS}=o(\mathrm{R})$ is known. BenDavidKothari18 ABIKPS17
Cheat-sheet functions total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) The inequality runs $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], i.e. $\mathrm{RS}=O(\mathrm{R})=\widetilde O(n)$, not the other way round. Floors: $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$, and $\mathrm{R}=O(\mathrm{RS}^2\log\mathrm{RS})$ for total $f$ [Thm 32] gives the same $\widetilde\Omega(\sqrt n)$. Pinning this cell would settle whether sabotage sees cheat-sheet hardness. BenDavidKothari18
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/2})\) The sabotage inequality runs $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], i.e. $\mathrm{RS}=O(\mathrm{R})$, so the recorded $\mathrm{R}=\widetilde\Omega(n^3)$ gives no floor. What does: $\mathrm{R}=O(\mathrm{RS}^2\log\mathrm{RS})$ for total $f$ [Thm 32], hence $\mathrm{RS}=\widetilde\Omega(\sqrt{\mathrm{R}})=\widetilde\Omega(n^{3/2})$; the weaker $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}$ only gives $\widetilde\Omega(n)$. Since no total function with $\mathrm{RS}=o(\mathrm{R})$ is known, the truth is probably $\widetilde\Theta(n^3)$, but that is not a theorem. BenDavidKothari18
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) The sabotage inequality runs the other way from what one might expect: $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{RS}=O(\mathrm{R})=\widetilde O(n^2)$ is the ceiling. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(n^{4/3})$, which happens to coincide with the recorded $\mathrm{R}$ floor. BenDavidKothari18
Gilmer-Saks-Srinivasan functions total \(\Omega(n),\ O(n^2)\) The sabotage inequality runs $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{R}$ is the ceiling, $\mathrm{RS}=O(\mathrm{R})=O(n^2)$. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\Theta(n)$, which matches the recorded $\mathrm{R}$ floor. BenDavidKothari18
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) The sabotage inequality runs $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{R}$ is the ceiling: $\mathrm{RS}=O(\mathrm{R})\le O(\mathrm{D})=\widetilde O(n)$. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$. BenDavidKothari18
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) The sabotage inequality is $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{R}=\widetilde\Theta(n^{2/3})$ is only the ceiling. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(n^{1/3})$; the alternative $\mathrm{R}=O(\mathrm{RS}^2\log\mathrm{RS})$ [Thm 32] gives the same $\widetilde\Omega(n^{1/3})$. Since no total function with $\mathrm{RS}=o(\mathrm{R})$ is known the truth is presumably $\widetilde\Theta(n^{2/3})$, but that is not a theorem. BenDavidKothari18
Ambainis' exact-quantum function total \(3^d\) putative The inequality runs $\mathrm{R}_\varepsilon\ge\bar{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], i.e. $\mathrm{RS}=O(\mathrm{R})=O(3^d)$, not $\mathrm{RS}\ge\mathrm{R}$. The matching floor is direct: sabotage the all-zero input at one coordinate $i$. Both completions are legal ($\mathrm{NE}^d(0^n)=0$ while every weight-one input gives $1$), and every query to $j\ne i$ returns $0$, so nothing about $i$ leaks until it is queried; against the uniform distribution on the $3^d$ choices of $i$ a deterministic solver needs $(3^d+1)/2$ queries in expectation, and Yao gives $\mathrm{RS}=\Omega(3^d)$. BenDavidKothari18
FORRELATION partial \(\widetilde O(\sqrt n)\) From the partial-function chain $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$. Nothing pins it from below: $\mathrm{CA} \le \mathrm{RS}$ is the only lower bound available and $\mathrm{CA}$ itself is unpinned here.
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) From $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$.
Simon's problem partial \(O(2^{n/2})\) From $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$.
Deutsch-Jozsa partial \(\Theta(1)\) At most $\bar\chi = \Theta(1)$; finding a $\ast$ in a sabotaged input is as easy as the problem itself here.
Bernstein-Vazirani partial \(O(n)\) $\mathrm{RS} = O(\bar\chi) = O(\mathrm{R}) = O(n)$.
Gap-Majority partial \(O(\min(\sqrt n, 1/\delta))\) $\mathrm{RS} = O(\bar\chi)$. Together with $\mathrm{CA} \le \mathrm{RS}$ this pins $\mathrm{RS} = \Theta(1/\delta)$ in the standard regime $\delta \ge 1/\sqrt n$. Note $\mathrm{R} = O(\mathrm{RS}^2\log \mathrm{RS})$ is a total-function statement, and gapped majority is exactly where it fails.
Gap-Majority at constant gap partial \(O(1)\) $\mathrm{RS} = O(\bar\chi)$. Note $\mathrm{R} = O(\mathrm{RS}^2\log\mathrm{RS})$ is a total-function statement.
Approximate index partial \(O(\sqrt{k\log k})\) $\mathrm{RS} = O(\bar\chi) = O(\mathrm{R})$.
Collision problem partial \(\Theta(1)\) The reason sabotage complexity is a total-function measure. A one-to-one table and a two-to-one table can agree on at most one point of each of the $n/2$ pairs, so they differ in $\ge n/2$ of the $n$ cells (the same counting as $\mathrm{CG}^{\mathrm{pub}}$ above). Every sabotaged input therefore carries $\ge n/2$ stars, and one uniformly random query finds a star with probability $\ge 1/2$: $\mathrm{RS} \le 2$. From below $\mathrm{RS} \ge \mathrm{CA} = \Omega(1)$. [BenDavidKothari18, Sec. 1.4] state it exactly so -- "any sabotaged input to the collision problem has at least half the bits sabotaged making $\mathrm{RS}(f) = O(1)$, but $\mathrm{R}(f) = \Omega(\sqrt n)$" -- as the reason their quadratic upper bound $\mathrm{R} = O(\mathrm{RS}^2\log\mathrm{RS})$ has to assume totality. BenDavidKothari18
Element distinctness total \(\Theta(n)\) Between $\mathrm{CA} = \Theta(n)$ and $\mathrm{R} = \Theta(n)$; equivalently $\bar{\mathrm{R}} \ge (1-2\varepsilon)\mathrm{RS}$ above and $\bar\chi = \Omega(\mathrm{RS})$ is consistent below. BenDavidKothari18
Ambainis-Belovs function partial \(O(n)\) From $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R}) = O(n)$.
Surjectivity total \(\Theta(n)\) putative Upper: $\mathrm{RS}(f)\le\mathrm{R}(f)=\Theta(n)$ for total $f$ [BenDavidKothari18]. Lower: take the surjective input that puts value $v$ in slot $v$ for $v\le R$ and value $1$ in the other $R$ slots. Starring any one bit of any of the first $R$ slots sabotages it: flipping that bit turns slot $v$ into a slot holding some other value $w\ne v$, which is still covered elsewhere, so the value $v$ goes missing and surjectivity flips. Those $R\log_2 R=\Theta(n)$ sabotaged inputs share one base assignment and each has a unique star, so finding a star is finding a marked coordinate among $\Theta(n)$. BenDavidKothari18
$k$-distinctness total \(\Theta(n)\) putative Upper: $\mathrm{RS}\le\mathrm{R}=\Theta(n)$ [BenDavidKothari18]. Lower: take the input consisting of $n/(k-1)$ values each repeated exactly $k-1$ times -- a $0$-input with no room to spare. Starring any single symbol sabotages it: left alone its group stays at $k-1$ copies, changed to another group it makes that group $k$. So all $n$ symbols are sabotage positions over one base input, and finding the $\ast$ is finding a marked symbol among $n$. BenDavidKothari18
Triangle finding total \(\Theta(m^2)\) putative Upper: $\mathrm{RS}\le\mathrm{R}=\Theta(m^2)$ [BenDavidKothari18]. Lower: start from the complete bipartite graph $K_{m/2,m/2}$, which is triangle-free, and note that adding any one of the $2\binom{m/2}2=\Theta(m^2)$ missing intra-side edges creates a triangle, since two vertices on the same side always share a neighbour. Starring any one of those edges sabotages the input, so finding a $\ast$ is finding a marked coordinate among $\Theta(m^2)$. BenDavidKothari18
Ordered search partial \(\Theta(\log n)\) putative The fixed coordinates of a sabotaged input must still be $0$s before $1$s, so a $\ast$ that matters always lies in the gap between the last fixed $0$ and the first fixed $1$; binary search on that gap finds one in $\lceil\log_2 n\rceil$ queries. For the lower bound, the $n$ inputs $0^{i-1}\ast1^{n-i}$ each have a unique correct answer, so a tree needs $n$ leaves. BenDavidKothari18
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)/(1-2\varepsilon)$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(n)$ meets $\mathrm{R} = \Theta(n)$.
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Lower: sabotage complexity composes perfectly, $\mathrm{RS}(f\circ g) \ge \mathrm{RS}(f)\mathrm{RS}(g)$ [BenDavidKothari18], and a sabotaged $\mathrm{AND}_k$ or $\mathrm{OR}_k$ with a single $\ast$ needs $\Theta(k)$ queries to locate it, so $\mathrm{RS} \ge \mathrm{RS}(\mathrm{AND}_m)\mathrm{RS}(\mathrm{OR}_{m^2}) = \Omega(m^3)$. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(m^3)$. Note this is a full $\mathrm{N}^{1/3}$ above $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(m^2)$. BenDavidKothari18
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)/(1-2\varepsilon)$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(m)$ meets $\mathrm{R} = \Theta(m)$.
Scorpion graphs total \(\Theta(m)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)/(1-2\varepsilon)$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(m)$ meets $\mathrm{R} = \Theta(m)$. So the scorpion composes perfectly: $\mathrm{R}(\mathrm{SCORP}_m \circ g^N) = \Omega(m\,\mathrm{R}(g))$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)/(1-2\varepsilon)$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(m^2)$ meets $\mathrm{R} = \Theta(m^2)$. Connectivity therefore composes perfectly: $\mathrm{R}(\mathrm{CONN}_m \circ g^N) = \Omega(N\,\mathrm{R}(g))$.
Meiburg’s parity-pointer family total \(O(q^3\log q)\) Meiburg26composition
Meiburg’s majority-pointer family total \(O(q^3\log q)\) Meiburg26composition
Meiburg’s parity-masked majority family total \(\Theta(q^3\log q)\) Meiburg26composition