\(\mathrm{COL}_n\)
Collision problem
$\mathrm{Q}=\Theta(n^{1/3})$ vs $\mathrm{R}=\Theta(\sqrt n)$: a polynomial-only quantum speedup for a promise problem.
partial quantum arity: a function table $g:[n]\to[n]$
Description
Promise: $g$ is one-to-one or two-to-one. Decide which.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(n^{1/3})\) | Upper: the birthday-paradox-plus-Grover algorithm of [BHT98]. Lower: the polynomial method [AaronsonShi04], originally for range $\Omega(n^2)$; [Kutin05] removed the range restriction (their proof needed range $\ge 3n/2$) and simplified the argument, and [Ambainis05smallrange] handles small ranges too. BHT98 AaronsonShi04 Kutin05 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(\sqrt n)\) | Birthday paradox both ways. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(n^{1/3})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{1/3})$ here. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(\sqrt n)\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon}(f) = \Theta(\sqrt n)$ here. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(n^{1/3})\) | Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(n^{1/3})$ here. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(1)\) | The certificate complexity barrier at its sharpest: a collision pair certifies a $2$-to-$1$ input with $2$ queries, and the promise means $O(1)$ queries also certify $1$-to-$1$-ness against the promise, so $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = O(1)$ while $\mathrm{Q} = \Theta(n^{1/3})$. No positive-weight adversary matrix can prove anything here -- this promise problem is the reason the negative-weights version had to be invented. HoyerSpalek05 SpalekSzegedy06 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n/2+1\) putative | Exactly. Upper: a two-to-one $g$ takes only $n/2$ values, so any $n/2+1$ queries repeat one; a one-to-one $g$ never does. Lower: an adversary answering with fresh values keeps both promises alive for $n/2$ queries, since $k \le n/2$ distinct answers can always be extended to a two-to-one function (put the $k$ queried points in $k$ different pairs). |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n/2+1\) putative | The same $n/2+1$ positions, fixed in advance. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(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. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(\sqrt n)\) putative | Sampling $c\sqrt n$ positions is non-adaptive and finds a collision with constant probability; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(\sqrt n)$. Adaptivity is worth nothing here. |
| \(\mathrm{C}(f)\) Certificate complexity | \(n/2+1\) putative | $\mathrm{C}^0 = n/2+1$ by the extension argument above; $\mathrm{C}^1 = 2$, a colliding pair. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(2\) putative | A colliding pair, on the two-to-one side. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(n/2+1\) putative | The one-to-one side: $n/2$ distinct answers can always be extended to a two-to-one $g$, so nothing short of $n/2+1$ certifies injectivity against the promise. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(2\) putative | The two-to-one side: one colliding pair. |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | Counting a query as one evaluation of $g$. Changing $g$ at a single point never stays in the promise: from a one-to-one $g$ it creates at most one collision, while a two-to-one $g$ needs all $n/2$ pairs to collide; from a two-to-one $g$ it orphans exactly one pair. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = n/2+1$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(0\) putative | See $\mathrm{s}$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(0\) putative | See $\mathrm{s}$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(2\) putative | Crossing between the two sides forces a change in each of the $n/2$ pairs, so every sensitive block has $\ge n/2$ of the $n$ coordinates: at most two disjoint ones, and two transversals of the pairing achieve it. $\mathrm{bs}^0 = \mathrm{bs}^1 = 2$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(2\) putative | See $\mathrm{bs}$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(2\) putative | See $\mathrm{bs}$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(2\) putative | Fractionally the same: $(n/2)\sum_B w_B \le \sum_i \mathrm{load}(i) \le n$. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(2\) | Equal to $\mathrm{fbs}$ by LP duality. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(1)\) putative | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$: rejecting one fixed input of the other type needs only a random query into a block where the two differ. Against $\mathrm{R} = \Theta(\sqrt n)$ and $\mathrm{Q} = \Theta(n^{1/3})$, this is why no certificate-style bound can prove anything about the collision problem. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(n/2+1\) putative | Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $n/2+1$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(n/2+1\) putative | Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $n/2+1$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(O(n)\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = n/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: a two-to-one $g$ has $n/2$ collision pairs, so the width-$2$ collision certificates overlap heavily and no unambiguous family of constant width covers that side. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(\sqrt n)\) | By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(\sqrt n)$. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(0\) putative | Exactly the argument recorded at \(\mathrm{SIMON}_n\): a rectangle $\prod_i S_i$ of functions that contains a $1$-$1$ function $g$ and a two-to-one function $h$ also contains the hybrids that copy one, then two, of $h$'s colliding positions into $g$, and one of those two hybrids has exactly one repeated value -- neither $1$-$1$ nor two-to-one, hence off the promise. So every product distribution inside the promise is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \Theta(\sqrt n)$. Contrast \(\mathrm{ED}_n\), the total version, where the uniform product distribution gives $\mathrm{D}^{\mathrm{prod}} = \Theta(n)$: the promise, not the collision structure, is what kills the measure. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(n^{1/3})\) | $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(n^{1/3})$. Note $\mathrm{Adv} = O(1)$ on the same problem: the general adversary is exactly what the positive one cannot see. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Theta(n^{1/3})\) | The [AaronsonShi04]/[Kutin05] lower bound is a degree bound -- that is what the polynomial method proves -- so $\widetilde{\deg} = \Omega(n^{1/3})$; and $\widetilde{\deg} \le 2\mathrm{Q} = O(n^{1/3})$. Approximate degree is thus the tight measure for the collision problem, where $\mathrm{Adv}$ collapses to $O(1)$. AaronsonShi04 Kutin05 |
| \(\deg(f)\) Exact degree | \(\Omega(n^{1/3})\) | $\deg \ge \widetilde{\deg} = \Omega(n^{1/3})$, in the standard encoding of the table by indicator variables $x_{i,v}$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(O(n^{1/3})\) | $\mathrm{sdeg} \le \widetilde{\deg}_{+} \le \widetilde{\deg} = O(n^{1/3})$. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(O(n^{1/3})\) | Between $\mathrm{sdeg}$ and $\widetilde{\deg} = O(n^{1/3})$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(n^{1/3})\) | $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg}_\varepsilon = O(n^{1/3})$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(n^{1/3})\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n^{1/3})$. MahadevdeWolf15 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(2\) putative | Exactly $2$: the polynomial $\sum_{i<j}\sum_v x_{i,v}x_{j,v}$ counts colliding pairs, so it is nonzero precisely on the two-to-one side, and no linear form can do that. Equivalently $\mathrm{ndeg} \le \mathrm{C}^1 = 2$. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(1\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = 1$: one nondeterministic quantum query, against $\mathrm{Q} = \Theta(n^{1/3})$ and $\mathrm{R} = \Theta(\sqrt n)$. Guessing a colliding pair is free; finding one is not. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$; a colliding pair is a two-query certificate and the promise makes it checkable. Aaronson08 |
| \(\lambda(f)\) Spectral sensitivity | \(0\) putative | The sensitivity graph on the promise is empty (see $\mathrm{s} = 0$: no single change of the table stays inside the promise), so $\lambda = 0$ while $\mathrm{Q} = \Theta(n^{1/3})$. Huang's $\deg \le \lambda^2$ is a total-function theorem. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(1)\) putative | Both players output the same uniformly random position $i$. A two-to-one $g$ and a one-to-one $g'$ can agree only on a set where $g$ is injective, i.e. on at most one point of each of the $n/2$ pairs, so they differ on $\ge n/2$ positions and the strategy wins with probability $\ge 1/2$. Hence $\mathrm{CG}^{\mathrm{pub}} \le 2$, and $\ge \mathrm{fbs} = 2$. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(1)\) | Between $\mathrm{CG}^{\mathrm{ns}} \ge 1$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(1)\) | Between $1$ and $\mathrm{CG}^{*}$. CGLMSG23 |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(1)\)· | $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}}) = \Theta(1)$, with $\mathrm{CA} \ge \mathrm{fbs} = 2$ from below. So both adversary methods fail on the collision problem: the positive quantum one by the certificate barrier ($\mathrm{Adv} = O(1)$) and the classical one for the same combinatorial reason, while $\mathrm{R} = \Theta(\sqrt n)$. CGLMSG23 |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(O(n)\) putative | Private coins: both players output a uniformly random position, winning with probability $|\Delta|/n^2 \ge 1/(2n)$. The total-function sandwich $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = O(n)$ happens to give the same bound but is not available on a promise problem, so the strategy is the proof. From below only $\Omega(\mathrm{CG}^{\mathrm{pub}}) = \Omega(1)$. CGLMSG23 |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(O(\sqrt n)\) putative | Uniform weights $w_i = \sqrt{2/n}$: two inputs of different value differ in $\ge n/2$ positions, so their weighted product is $\ge 1$, at cost $\sqrt{2n}$. From below $\mathrm{EC} \ge \mathrm{fbs} = 2$. Not via $\mathrm{EC} \le \mathrm{C}$, which is a total-function statement. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(n)\) putative | With $1$ = "two-to-one": an algorithm that is certain on the $1$-side never outputs $0$ on a two-to-one input, so whenever it does output $0$ it must hold a $0$-certificate, i.e. $n/2+1$ distinct values. It must do so with probability $\ge 2/3$ on one-to-one inputs, so $\mathrm{R}^1 = \Omega(n)$; and $\mathrm{R}^1 \le \mathrm{D} = n/2+1$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(O(n)\) | At most $\mathrm{R}_0 = n/2+1$; at least $\mathrm{Q} = \Omega(n^{1/3})$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(O(n)\) | At most $\mathrm{D} = n/2+1$; at least $\mathrm{Q}_0 = \Omega(n^{1/3})$. |
| \(\chi(f)\) Conflict complexity | \(O(\sqrt n)\) | $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(\sqrt n)$. The lower bound $\chi = \Omega(\mathrm{bs})$ [Li18] is total-only and would give only $\Omega(1)$ anyway. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Omega(n^{1/4})\) | $\mathrm{R} = O(\bar\chi^2)$ holds for partial $g$, so $\bar\chi = \Omega(\sqrt{\mathrm{R}}) = \Omega(n^{1/4})$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(\sqrt n)$. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Omega(n^{1/4})\) | $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ and $\mathrm{LR} \le \mathrm{R} = O(\sqrt n)$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\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 |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Omega(n^{1/3})\) | $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(n^{1/3})$ since quantum query complexity composes perfectly, and $\mathrm{R}^{*} \le \mathrm{R} = O(\sqrt n)$. Whether iterated collision-finding costs $n^{1/3}$ or $n^{1/2}$ per level is open. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(O(\sqrt n)\) | Between $\widetilde{\deg} = \Theta(n^{1/3})$ and $\mathrm{R} = \Theta(\sqrt n)$. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(O(\sqrt n)\) | $\mathrm{noisyR} \le \mathrm{R}$. The implication "$\mathrm{R} = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$" does not apply, since $\mathrm{R} = \Theta(\sqrt n)$ and the arity is $n$. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Theta(\sqrt n)\) | Between $\mathrm{R}$ and $O(\mathrm{R}\log\mathrm{R})$: repeat each read $O(\log n)$ times to make the whole transcript reliable. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(O(\sqrt n)\) | $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(\sqrt n)$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(O(\sqrt n)\) | $\overline{\mathrm{prt}} \le \mathrm{prt}$. |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde\Theta(n^{1/3})\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(O(n)\) | At most $\mathrm{D} = n/2+1$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(\sqrt n)\) | Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(\sqrt n)$. (The search version -- find a collision -- is the one where pseudo-determinism bites; the decision version has a unique answer.) |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(2\) | Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. GoosPitassi14 |
| \(\mathrm{rdeg}(f)\) Rational degree | \(O(n)\) | At most $\mathrm{C} = n/2+1$; from below $\mathrm{rdeg} \ge \mathrm{ndeg} = 2$ and $\mathrm{rdeg} \ge \widetilde{\mathrm{rdeg}}$. |
Separations its values prove — computed, not recorded
Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 53 in total, strongest first.
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{RS}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{RS}(f) = \Theta(1)\)
-
\(\mathrm{R}^{*}(f_n) \to \infty \ \text{ while } \ \mathrm{fbs}(f_n) = O(1)\)from \(\mathrm{R}^{*}(f) = \Omega(n^{1/3})\) against \(\mathrm{fbs}(f) = 2\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{NQ}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{NQ}(f) = 1\)
-
\(\mathrm{Q}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{FC}(f_n) = O(1)\)from \(\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{1/3})\) against \(\mathrm{FC}(f) = 2\)
-
\(\deg(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\deg(f) = \Omega(n^{1/3})\) against \(\mathrm{cbs}(S) = 2\)
-
\(\widetilde{\deg}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{CA}(f_n) = O(1)\)from \(\widetilde{\deg}_{\varepsilon}(f) = \Theta(n^{1/3})\) against \(\mathrm{CA}(f) = \Theta(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{RS}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{RS}(f) = \Theta(1)\)
-
\(\mathrm{R}^{*}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{R}^{*}(f) = \Omega(n^{1/3})\) against \(\mathrm{C}^1(f) = 2\)
-
\(\mathrm{Q}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{1/3})\) against \(\mathrm{cbs}(S) = 2\)
-
\(\deg(f_n) \to \infty \ \text{ while } \ \mathrm{FC}(f_n) = O(1)\)from \(\deg(f) = \Omega(n^{1/3})\) against \(\mathrm{FC}(f) = 2\)
-
\(\widetilde{\deg}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{\mathrm{pub}}(f_n) = O(1)\)from \(\widetilde{\deg}_{\varepsilon}(f) = \Theta(n^{1/3})\) against \(\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{RS}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{RS}(f) = \Theta(1)\)
-
\(\mathrm{R}^{*}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{R}^{*}(f) = \Omega(n^{1/3})\) against \(\mathrm{C}_{\min}(f) = 2\)
-
\(\mathrm{Q}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{*}(f_n) = O(1)\)from \(\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{1/3})\) against \(\mathrm{CG}^{*}(f) = \Theta(1)\)
… and 39 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Quadratic: $\mathrm{R}_0 = n/2+1$ against $\mathrm{R} = \Theta(\sqrt n)$.
-
Unbounded: $\mathrm{R} = \Theta(\sqrt n)$ against $\mathrm{RS} = \Theta(1)$. This is the separation that confines $\mathrm{R} = O(\mathrm{RS}^2\log\mathrm{RS})$ to total functions [BenDavidKothari18, Sec. 1.4].
-
Unbounded: $\bar\chi = \Omega(\sqrt{\mathrm{R}}) = \Omega(n^{1/4})$ against $\mathrm{RS} = \Theta(1)$. Max-conflict complexity dominates sabotage complexity [GLSS19, Thm 7] and here it does so by an unbounded margin -- which is the point of introducing it.
-
Unbounded: $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}}) = \Omega(n^{1/4})$ against $\mathrm{RS} = \Theta(1)$.
Cited as a witness by
-
\(\mathrm{Adv}(\mathrm{Col}) = O(1) \text{ while } \mathrm{Adv}^{\pm}(\mathrm{Col}) = \Theta(n^{1/3})\)
-
\(\mathrm{R}(\mathrm{COL}_n) = \Theta(\sqrt n) \quad\text{against}\quad \mathrm{RS}(\mathrm{COL}_n) = \Theta(1)\)
-
\(\bar\chi(\mathrm{COL}_n) = \Omega(n^{1/4}) \quad\text{against}\quad \mathrm{RS}(\mathrm{COL}_n) = \Theta(1)\)