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