Q The Query Complexity Zoo
\(\mathrm{GapMaj}^{\delta}_{n}\)

Gap-Majority

The universal "hardest easy" promise problem; characterises noisy randomized complexity.

partial separating arity: $n$ bits

Description

Promise $\big||x| - n/2\big| \ge \delta n$; output $1$ if $|x| \ge n/2+\delta n$ and $0$ if $|x| \le n/2-\delta n$.

Formal definition

$\mathrm{GapMaj}^\delta_n(x) = \mathbb{1}[|x| > n/2]$ restricted to $\{x : \big||x|-n/2\big| \ge \delta n\}$.

Measure values

MeasureValueNotes
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\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
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(n)\) Independent of $\delta$, and the whole point of the example: $\mathrm{D}$ is unbounded in terms of $\mathrm{R}$ on partial functions. Adversary count: after $q$ queries returning $a$ ones, output $0$ is still consistent iff $a \le n/2-\delta n$ and output $1$ iff $a + (n-q) \ge n/2+\delta n$, so keeping both alive is possible exactly while $q \le (1-2\delta)n$ -- giving $\mathrm{D} = (1-2\delta)n + 1$ up to integrality, and $n$ queries always suffice.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(\min(n, 1/\delta^2))\) putative Equal to $\mathrm{R}$: buying bias buys nothing here, which is exactly why $\mathrm{GapMaj}$ is the universal inner function of [CKMPSS23] (Theorem 4: $\mathrm{noisyR}(f) = \Theta(\mathrm{R}(f \circ \mathrm{GapMaj}_n)/n)$, with their $\mathrm{GapMaj}_n$ the $\delta = 2/\sqrt{n}$ instance). Upper: $\mathrm{noisyR} \le \mathrm{R}$ always. Lower: let $\mu^{\pm}$ be uniform on the two Hamming levels, so each coordinate is marginally $\mathrm{Bern}(1/2 \pm \delta)$. A noisy query of bias $\gamma$ returns a bit distributed $\mathrm{Bern}(1/2 \pm \gamma\delta)$, and $\mathrm{KL} = O(\gamma^2\delta^2)$, while the query costs $\gamma^2$. Distinguishing $\mu^+$ from $\mu^-$ needs $\Omega(1)$ total divergence, so the cost $\sum_j \gamma_j^2$ is $\Omega(1/\delta^2)$. CKMPSS23
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\min(n, 1/\delta))\) Amplitude estimation of $|x|/n$ to additive $\delta$; the matching lower bound is the usual approximate-counting bound of [NayakWu99]. So the promise buys a quadratic quantum speed-up over $\mathrm{R}$, the same one as for approximate counting. NayakWu99
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta\!\big(\sqrt{\mathrm{R}}\big) = \Theta\!\big(\min(\sqrt n, 1/\delta)\big)\)· The extreme case of the $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R}$ sandwich, and the reason the measure was introduced: a single query already gives bias $\Theta(\delta)$ towards the answer, and $\mathrm{LR}$ charges $1/\gamma$ rather than $1/\gamma^2$ for bias $\gamma$. So gapped majority is cheap for $\mathrm{LR}$ and expensive for $\mathrm{R}$, which is exactly the slack that makes randomized composition fail. BBGM22
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta\!\big(\min(\sqrt n, 1/\delta)\big)\)· At most $\mathrm{LR}$, and at least $\Omega(\sqrt{\mathrm{R}})$ -- the bound $\mathrm{R} = O(\bar\chi^2)$ holds for partial $g$, unlike its $\chi$ analogue -- so both ends meet. Since $\bar\chi$ is the quantity that appears in the composition theorem $\mathrm{R}(f \circ g^n) = \Omega(\mathrm{R}(f)\bar\chi(g))$, gapped majority as an inner function loses a square root -- which is precisely why $\mathrm{R}$ does not compose. GLSS19
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n)\) Exactly $n/2 - \delta n + 1$ on both sides, for every $\delta$. A $1$-certificate must fix that many ones: fix fewer and setting all free coordinates to $0$ leaves a completion that is still inside the promise and is a $0$-input. Symmetrically for $\mathrm{C}^0$. Note this is not $\Theta(\mathrm{D})$ by accident -- here $\mathrm{C}$, $\mathrm{C}^0$, $\mathrm{C}^1$ and $\mathrm{D}$ all coincide up to the additive $1$.
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(\min(n, 1/\delta))\) Every sensitive block at a promise input must move at least $2\delta n$ coordinates, so disjoint blocks number at most $1/(2\delta)$; and at an input of weight exactly $n/2+\delta n$ that many disjoint blocks of $2\delta n$ ones each do flip the answer.
\(\mathrm{s}(f)\) Sensitivity \(0\) putative Whenever $2\delta n > 1$. A single flip moves $|x|$ by one, and the value only changes on crossing $n/2$, which the promise puts $2\delta n$ away; so the flipped input is either outside the promise or has the same value. Sensitivity is therefore identically zero while $\mathrm{bs} = \Theta(\min(n,1/\delta))$ and $\mathrm{D} = \Theta(n)$: the promise-function counterexample to every bound with $\mathrm{s}$ on the small side.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(n)\) Every certificate on either side has $n/2-\delta n+1$ coordinates, so the min over inputs equals the max: $\mathrm{C}_{\min} = \mathrm{C} = \mathrm{D}$ up to $\pm 1$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) putative A zero-error run must end on a certificate, so $\mathrm{R}_0 \ge \mathrm{C} = \Theta(n)$; and $\mathrm{R}_0 \le \mathrm{D}$. At constant $\delta$ this is an unbounded $\mathrm{R}_0$-vs-$\mathrm{R}$ gap.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\Theta(n)\) Between $\mathrm{D} = \Theta(n)$ and the trivial $n$; the adversary count for $\mathrm{D}$ never used adaptivity anyway.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(\min(n, 1/\delta^2))\) Sampling is non-adaptive, and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(\min(n, 1/\delta^2))\) Squeezed between $\mathrm{noisyR}$ and $\mathrm{R}^{\mathrm{na}}$, which coincide here; equivalently, Theorem 8 of [BenDavidBlais20composition] applied to a partial function. Every corner of the square -- adaptive or not, noisy or not -- costs $\Theta(\min(n,1/\delta^2))$, which is part of what makes $\mathrm{GapMaj}$ the right universal inner function. BenDavidBlais20composition
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(\min(n, 1/\delta^2))\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) putative See $\mathrm{s}$: identically zero on both sides, whenever $2\delta n > 1$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) putative See $\mathrm{s}$: identically zero on both sides, whenever $2\delta n > 1$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(\min(n, 1/\delta))\) putative The count in $\mathrm{bs}$ is symmetric under complementation, so $\mathrm{bs}^0 = \mathrm{bs}^1 = \mathrm{bs}$: at an input of weight exactly $n/2-\delta n$, disjoint blocks of $2\delta n$ zeros each flip the answer, and no sensitive block is smaller.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\Theta(\min(n, 1/\delta))\) putative See $\mathrm{bs}^0$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(n)\) Exactly $n/2-\delta n+1$; see $\mathrm{C}$, which is attained on both sides.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(n)\) Exactly $n/2-\delta n+1$; see $\mathrm{C}$, which is attained on both sides.
\(\lambda(f)\) Spectral sensitivity \(0\) putative The sensitivity graph on the promise has no edges at all (see $\mathrm{s}=0$), so $\lambda = 0$ while $\deg = \Theta(n)$. Huang's theorem $\deg \le \lambda^2$ is a total-function statement and $\mathrm{GapMaj}$ breaks it as badly as arithmetic allows.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(n)$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) putative Squeezed between $\mathrm{C}_{\min}$ and $\mathrm{UC}$, both $\Theta(n)$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(n)$.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(n)\) putative Squeezed between $\mathrm{C}_{\min}$ and $\mathrm{D}$, both $\Theta(n)$: with every certificate of full length there is no caterpillar structure to exploit.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n)}\) putative Every leaf subcube has codimension $\ge \mathrm{C}_{\min} = \Theta(n)$, giving $2^{\Omega(n)}$ leaves; and $\mathrm{DTsize} \le 2^{\mathrm{D}}$.
\(\deg(f)\) Exact degree \(\Theta(n)\) putative Exact degree ignores the promise gap entirely. Symmetrising, an exactly representing polynomial gives a univariate $p$ with $p(t) = 0$ for all $\lfloor n/2-\delta n\rfloor + 1$ integers $t \le n/2-\delta n$, so $\deg \ge (1/2-\delta)n$; and $\deg \le \mathrm{D} = \Theta(n)$. Against $\widetilde{\deg} = \Theta(\min(n,1/\delta))$ this is the cleanest $\deg$-vs-$\widetilde{\deg}$ gap there is.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\min(n, 1/\delta))\)· The Nayak-Wu lower bound for approximate counting is a degree bound, so it gives $\widetilde{\deg} = \Omega(\min(n,1/\delta))$; and $\widetilde{\deg} \le 2\mathrm{Q} = O(\min(n,1/\delta))$. NayakWu99
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) putative Exactness is as expensive as determinism: $\mathrm{Q}_E \ge \deg/2 = \Omega(n)$ and $\mathrm{Q}_E \le \mathrm{D} = \Theta(n)$. At constant $\delta$ this is an unbounded $\mathrm{Q}_E$-vs-$\mathrm{Q}$ gap.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(\min(n, 1/\delta))\) $\mathrm{RC} = \Theta(\mathrm{fbs})$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(\min(n, 1/\delta))\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(\min(n, 1/\delta^2))\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R}$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(0\) putative The support of a product distribution is a subcube: some coordinates are fixed, the rest free. If the fixed part has weight $w$ and there are $m$ free coordinates, the weights realised in the subcube are exactly the integers in $[w, w+m]$, an unbroken interval. Meeting both sides of the promise would mean the interval contains a weight $\le n/2 - \delta n$ and a weight $\ge n/2 + \delta n$, hence also every weight strictly between -- and those points are off the promise. So every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \Theta(\min(n, 1/\delta^2))$. See \(\mathrm{forr}\).
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(\min(n, 1/\delta^2))\) putative Read each sampled coordinate $O(1)$ times and majority-vote: $\mathrm{N}_p = O(\mathrm{R})$, and $\mathrm{N}_p \ge \mathrm{R}$ always.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\min(n, 1/\delta))\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\min(n, 1/\delta))\) Sandwiched between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\min(n, 1/\delta))\) $\gamma_2 = \Theta(\mathrm{Q})$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(\min(n, 1/\delta))\) putative Upper and lower, and neither uses a total-function theorem. Lower: $\mathrm{CA} \ge \mathrm{fbs} = \Theta(\min(n,1/\delta))$, which does survive on partial functions (\(\mathrm{CA}(f)\), settings note). Upper: $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}})$ and the shared-random-index strategy below wins with probability $2\delta$. So $\mathrm{CA}$ sees the $\Theta(1/\delta)$ but not the $\Theta(1/\delta^2)$ of $\mathrm{R}$: the classical adversary bound is quadratically weak exactly where bias-amplification is the real cost. CGLMSG23
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(\min(n, 1/\delta))\) putative Both players output the same uniformly random index. Inputs of different value differ in at least $2\delta n$ of the $n$ coordinates, so they win with probability $\ge 2\delta$ and $\mathrm{CG}^{\mathrm{pub}} \le 1/(2\delta)$; and $\mathrm{CG}^{\mathrm{pub}} \ge \mathrm{fbs}$. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(\min(n, 1/\delta))\) All three of $\mathrm{CG}^{\mathrm{ns}}, \mathrm{CG}^{*}, \mathrm{CG}^{\mathrm{pub}}$ collapse to $\Theta(\mathrm{CA})$ [CGLMSG23]; only the private-coin game escapes. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(\min(n, 1/\delta))\) See $\mathrm{CG}^{*}$. CGLMSG23
\(\mathrm{EC}(f)\) Expectational certificate complexity \(O(\sqrt{n/\delta})\) putative Uniform weights $w^x_i = (2\delta n)^{-1/2}$ at every input: two inputs of different value differ in $\ge 2\delta n$ coordinates, so their weighted product is $\ge 1$, at total cost $n/\sqrt{2\delta n} = \sqrt{n/(2\delta)}$. From below $\mathrm{EC} = \Omega(1/\delta)$: given weights of total mass $k$, take $x$ of weight $n/2+\delta n$ and let $\Delta$ be the $2\delta n$ lightest ones of $x$, whose total $w^x$-mass is at most $k\cdot 2\delta n/(n/2) = 4\delta k$; flipping them gives a $0$-input, and the constraint forces $4\delta k \ge 1$. So at constant $\delta$, $\mathrm{EC} = \Omega(1)$ and $O(\sqrt n)$ while $\mathrm{CA} = \Theta(1)$: the textbook chains $\mathrm{EC} \le \mathrm{C}$ and $\mathrm{R}_0 = O(\mathrm{EC}^2)$ are total-function statements and are not used.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(n)\) putative Parity queries are no better than plain ones. After $q$ parity queries the consistent inputs form an affine space $A$ of dimension $n-q$; picking $n-q$ free coordinates, $A$ contains an input of weight $\le q$ and one of weight $\ge n-q$. If $q < n/2-\delta n$ these are a $0$-input and a $1$-input of the promise, so no leaf can decide, giving $\mathrm{D}^{\oplus} \ge (1/2-\delta)n$; and $\mathrm{D}^{\oplus} \le \mathrm{D} = \Theta(n)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) putative Zero-error quantum is as expensive as determinism. If a $T$-query algorithm outputs $1$ with probability $p(x) \ge 1/2$ on $1$-inputs and $p(x) = 0$ on $0$-inputs, then $p$ is a non-negative polynomial of degree $\le 2T$, so its symmetrisation $\tilde p(t) = \mathbb{E}_{|x|=t}[p(x)]$ is a genuine univariate polynomial of degree $\le 2T$ vanishing at every integer $t \le n/2-\delta n$ -- that is $(1/2-\delta)n$ distinct roots -- and positive at $t \ge n/2+\delta n$. Hence $\mathrm{Q}_0 \ge (1/4-\delta/2)n$, and $\mathrm{Q}_0 \le \mathrm{R}_0 = \Theta(n)$. Against $\mathrm{Q} = \Theta(\min(n,1/\delta))$ this is an unbounded gap at constant $\delta$.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Theta(n)\) putative Same symmetrisation, applied to $p^2$: if $p$ is nonzero exactly on the $1$-inputs then $q(t) = \mathbb{E}_{|x|=t}[p(x)^2]$ is a non-negative univariate polynomial of degree $\le 2\,\mathrm{ndeg}$ vanishing at all $(1/2-\delta)n$ integers $t \le n/2-\delta n$ and nonzero above $n/2+\delta n$, so $\mathrm{ndeg} \ge (1/4-\delta/2)n$; and $\mathrm{ndeg} \le \mathrm{C}^1 = \Theta(n)$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(n)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = \Theta(n)$: nondeterministic quantum queries do not see the promise gap either.
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(n)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\} = \Theta(n)$, the two sides being symmetric. Exact rational approximation is therefore as hard as exact polynomial representation here, even though $\mathrm{rdeg}_{\varepsilon} = O(\min(n,1/\delta))$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(\min(n, 1/\delta))\) $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg}_\varepsilon = O(\min(n,1/\delta))$. Contrast the exact $\mathrm{rdeg} = \Theta(n)$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(\min(n, 1/\delta))\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(\min(n,1/\delta))$; postselection does not obviously help a problem that amplitude estimation already solves at that cost. MahadevdeWolf15
\(\mathrm{sdeg}(f)\) Sign degree \(1\) The single polynomial $p(x) = \sum_i x_i - n/2$ has the right sign at every promise input, whatever $\delta$ is. So $\mathrm{sdeg} = 1$ against $\deg = \Theta(n)$ and $\widetilde{\deg} = \Theta(\min(n,1/\delta))$ -- unbounded-error (the $\mathsf{PP}$ analogue) trivialises gapped majority.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(\min(n, 1/\delta))\) Between $\mathrm{sdeg} = 1$ and $\widetilde{\deg} = \Theta(\min(n,1/\delta))$. For $\delta \ge 1/8$ a degree-$1$ one-sided approximation exists, so the lower end is attained at constant $\delta$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Squeezed: $\mathrm{R}^1 \ge \mathrm{C}^1 = \Theta(n)$ (a certain "yes" must exhibit a $1$-certificate) and $\mathrm{R}^1 \le \mathrm{R}_0 = \Theta(n)$. One-sided error is already as expensive as no error at all.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt{\min(n, 1/\delta)})\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$, with $\mathrm{fbs} = \Theta(\min(n,1/\delta))$; and independently $\mathrm{QC} \le \mathrm{Q}$. Aaronson08
\(\chi(f)\) Conflict complexity \(O(\min(\sqrt n, 1/\delta))\) $\chi \le \bar\chi$. The matching lower bounds $\chi = \Omega(\mathrm{bs})$ [Li18] and $\mathrm{R} = O(\chi^2)$ are both total-function statements -- and the first is false here, since $\mathrm{bs} = \Theta(\min(n,1/\delta))$ can be quadratically larger.
\(\mathrm{RS}(f)\) Sabotage complexity \(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.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(O(\min(n, 1/\delta^2))\) $\mathrm{R}^{*} \le \mathrm{R}$, and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(\min(n,1/\delta))$ because quantum query complexity composes perfectly. Whether the limit sits at $\mathrm{R}$ or at $\mathrm{Q}$ is exactly the open question of [BBGM22].
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(\min(n, 1/\delta^2))\) Between $\widetilde{\deg} = \Theta(\min(n,1/\delta))$ and $\mathrm{R} = \Theta(\min(n,1/\delta^2))$; the conical-junta relaxation is not known to close that quadratic gap here.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(\min(n, 1/\delta^2))\) $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$; from below $(1-4\varepsilon)\mathrm{CA} \le \mathrm{prt}_\varepsilon + \log(1/\varepsilon)$ gives $\Omega(\min(n,1/\delta))$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(\min(n, 1/\delta^2))\) $\overline{\mathrm{prt}} \le \mathrm{prt}$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\widetilde\Theta(\min(n, 1/\delta))\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(\min(n, 1/\delta))\) $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(\min(n,1/\delta))$. The positive adversary is not obstructed here the way it is at \(\mathrm{COL}_n\) -- the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(n)$ is not binding -- but no matching lower bound is recorded.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(\min(n, 1/\delta))\) Same counting, fractionally: $2\delta n\sum_B w_B \le \sum_i\sum_{B \ni i} w_B \le n$. So $\mathrm{fbs} = \Theta(\mathrm{bs}) = O(1)$ at constant $\delta$ while $\mathrm{C} = \Theta(n)$ -- the promise-function counterexample to $\mathrm{C} = O(\mathrm{fbs}^2)$ and to $\mathrm{C} = O(\mathrm{RC}^2)$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(\min(n, 1/\delta^2))\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R})$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(\min(n, 1/\delta))\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = \Theta(\min(n,1/\delta))$. GoosPitassi14
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Omega(n)\) putative Private coins, and unlike $\mathrm{CG}^{\mathrm{pub}} = \Theta(\min(n,1/\delta))$ it does not shrink with $\delta$. Upper: each player outputs a uniformly random position on which its own input is $1$ (resp. $0$); the two inputs differ on $\ge 2\delta n$ such positions, giving $\mathrm{CG} = O(n/\delta)$. Lower: fix the $1$-player at $x$ with output distribution $p$, and let the $0$-player hold $y$ obtained from $x$ by zeroing the $2\delta n$ positions of $\mathrm{supp}(x)$ carrying the least $p$-mass. The win probability is at most $\max_{i \in \Delta} p(i)$, and the $2\delta n$-th smallest of the $\ge n/2$ values $\{p(i) : x_i = 1\}$ is at most $2/n$. So $\mathrm{CG} \ge n/2$. At constant $\delta$ this is $\Theta(n)$ against $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$: private randomness is the one variant of the four that escapes the collapse to $\mathrm{CA}$.

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. 23 in total, strongest first.

… and 9 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

Cited as a witness by