\(\mathrm{GapMaj}^{\delta}_{n}\)
Gap-Majority
The universal "hardest easy" promise problem; characterises noisy randomized complexity.
partial 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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = \Theta(n)\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\mathrm{NQ}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{NQ}(f) = \Theta(n)\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{rdeg}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{rdeg}(f) = \Theta(n)\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{ndeg}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{ndeg}(f) = \Theta(n)\) against \(\mathrm{s}^1(f) = 0\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{C}(f) = \Theta(n)\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\mathrm{NQ}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{NQ}(f) = \Theta(n)\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{rdeg}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{rdeg}(f) = \Theta(n)\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{ndeg}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{ndeg}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = 0\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{C}^0(f) = \Theta(n)\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\mathrm{NQ}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{NQ}(f) = \Theta(n)\) against \(\mathrm{s}^1(f) = 0\)
-
\(\mathrm{rdeg}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{rdeg}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = 0\)
-
\(\mathrm{ndeg}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{ndeg}(f) = \Theta(n)\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{C}^1(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{C}^1(f) = \Theta(n)\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\mathrm{NQ}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{NQ}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = 0\)
… and 9 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
At constant $\delta$, $\mathrm{D} = \Theta(n)$ while $\mathrm{R} = \Theta(1)$: the standard proof that $\mathrm{D}$ is unbounded in terms of $\mathrm{R}$ on partial functions.
-
Quadratic: $\mathrm{R} = \Theta(1/\delta^2)$ against $\mathrm{Q} = \Theta(1/\delta)$, the approximate-counting speed-up in its cleanest form.
-
At constant $\delta$, $\mathrm{C} = \Theta(n)$ while $\mathrm{fbs} = O(1)$: rounding a fractional certificate is a total-function argument.
-
Unbounded: $\mathrm{s} = 0$ identically (the promise gap is wider than one flip) while $\mathrm{bs} = \Theta(\min(n,1/\delta))$. Every measure sitting above $\mathrm{s}$ is unbounded in terms of it on partial functions, and $\mathrm{GapMaj}$ says so in one line.
-
At constant $\delta$, unbounded: $\mathrm{R} = \Theta(1)$ but $\mathrm{R}_0 = \Theta(n)$, because certainty forces a full certificate.
Cited as a witness by
-
\(\mathrm{R}(\mathrm{GapMaj}_n) = O(1),\ \ \mathrm{D}(\mathrm{GapMaj}_n) = \Omega(n)\)
-
\(\mathrm{fbs}(\mathrm{GapMaj}^{\delta}_n) \le 1/(2\delta),\ \ \mathrm{C}(\mathrm{GapMaj}^{\delta}_n) > n/2-\delta n\)