Q The Query Complexity Zoo
\(\mathrm{GapMaj}^{1/4}_{n}\)

Gap-Majority at constant gap

The $\delta = 1/4$ instance of Gap-Majority: $\Theta(1)$ for every bounded-error measure, $\Theta(n)$ for every exact one.

partial separating arity: $n$ bits

Description

Promise $\big||x| - n/2\big| \ge n/4$; output $1$ if $|x| \ge 3n/4$ and $0$ if $|x| \le n/4$. This is \(\mathrm{GapMaj}^{\delta}_{n}\) with the gap parameter frozen at $\delta = 1/4$, and it is the instance that does the separating: every $\Theta(\min(n,1/\delta))$ or $\Theta(\min(n,1/\delta^2))$ entry of the general family collapses to $\Theta(1)$ here, while the $\delta$-free entries stay at $\Theta(n)$.

Formal definition

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

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(n)\) Exactly $n/2 + 1$ up to integrality, by the adversary count of \(\mathrm{GapMaj}^{\delta}_{n}\) at $\delta = 1/4$: an adversary answering queries can keep both outputs alive for $(1-2\delta)n = n/2$ queries.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n)\) Exactly $n/4 + 1$ on both sides: a $1$-certificate must exhibit that many ones, or setting every free coordinate to $0$ leaves a $0$-input of the promise.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(n)\) See $\mathrm{C}$; attained on both sides.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(n)\) See $\mathrm{C}$; attained on both sides.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(n)\) Every certificate has the same length, so the min over inputs equals the max.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\Theta(n)\) Between $\mathrm{D}$ and $n$; the adversary count never used adaptivity.
\(\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}$. Against $\mathrm{R} = \Theta(1)$ this is the unbounded $\mathrm{R}_0$-vs-$\mathrm{R}$ separation on partial functions.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Squeezed between $\mathrm{C}^1$ and $\mathrm{R}_0$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) putative Between $\mathrm{C}$ and $\mathrm{D}$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) putative Between $\mathrm{C}_{\min}$ and $\mathrm{UC}$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) putative Between $\mathrm{C}$ and $\mathrm{D}$.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(n)\) putative Between $\mathrm{C}_{\min}$ and $\mathrm{D}$: with every certificate of full length there is no caterpillar structure to exploit.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(n)\) putative Parity queries do not help: after $q < n/4$ of them the consistent affine space still contains inputs of both values. See \(\mathrm{GapMaj}^{\delta}_{n}\).
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n)}\) putative Every leaf subcube has codimension $\ge \mathrm{C}_{\min} = \Theta(n)$; and $\mathrm{DTsize} \le 2^{\mathrm{D}}$.
\(\deg(f)\) Exact degree \(\Theta(n)\) putative Exact degree ignores the promise gap: symmetrising an exactly representing polynomial gives a univariate with $\Theta(n)$ forced roots. Against $\widetilde{\deg} = \Theta(1)$ this is the cleanest $\deg$-vs-$\widetilde{\deg}$ gap there is.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) putative Exactness costs as much as determinism: $\mathrm{Q}_E \ge \deg/2$ and $\mathrm{Q}_E \le \mathrm{D}$. Against $\mathrm{Q} = \Theta(1)$, unbounded.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) putative The polynomial argument of \(\mathrm{GapMaj}^{\delta}_{n}\): a zero-error algorithm's acceptance polynomial symmetrises to a non-negative univariate with $\Theta(n)$ roots. Against $\mathrm{Q} = \Theta(1)$, unbounded.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Theta(n)\) putative Same symmetrisation applied to $p^2$; and $\mathrm{ndeg} \le \mathrm{C}^1$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(n)\) $\mathrm{NQ} = \lceil\mathrm{ndeg}/2\rceil$.
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(n)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$, the two sides being symmetric. Against $\mathrm{rdeg}_\varepsilon = \Theta(1)$ and $\mathrm{Q} = \Theta(1)$: on partial functions rational degree is unbounded in terms of everything bounded-error, which is why What is the exponent of … versus …? is a total-function question.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(n)\) putative Private coins, and unlike $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$ it does not shrink with the gap: see the two-sided argument at \(\mathrm{GapMaj}^{\delta}_{n}\).
\(\mathrm{s}(f)\) Sensitivity \(0\) putative A single flip moves $|x|$ by one and the promise puts the two sides $n/2$ apart, so no promise input has a sensitive coordinate at all.
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) putative See $\mathrm{s}$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) putative See $\mathrm{s}$.
\(\lambda(f)\) Spectral sensitivity \(0\) putative The sensitivity graph on the promise has no edges, so $\lambda = 0$ while $\deg = \Theta(n)$. Huang's $\deg \le \lambda^2$ is a total-function theorem and this breaks it as badly as arithmetic allows.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(0\) putative The support of a product distribution is a subcube, whose realisable Hamming weights form an unbroken interval; an interval meeting both sides of the promise would have to contain the forbidden middle. So every product $\mu$ is one-sided.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(1)\) Sample $O(1)$ coordinates and take the empirical majority; $\Theta(1/\delta^2)$ at $\delta = 1/4$. Against $\mathrm{D} = \Theta(n)$ this is the standard proof that $\mathrm{D}$ is unbounded in terms of $\mathrm{R}$ on partial functions. BenDavidBlais20composition
\(\mathrm{bs}(f)\) Block sensitivity \(1\) A sensitive block must move at least $2\delta n = n/2$ coordinates, and an input of weight $3n/4$ has room for exactly one such block.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(1\) putative Symmetric under complementation; see $\mathrm{bs}$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(1\) putative See $\mathrm{bs}^0$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(1)\) At most $1/(2\delta) = 2$ by the counting $2\delta n\sum_B w_B \le n$. So $\mathrm{fbs} = \Theta(1)$ against $\mathrm{C} = \Theta(n)$: the promise counterexample to $\mathrm{C} = O(\mathrm{fbs}^2)$.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(1)\) $\mathrm{RC} = \Theta(\mathrm{fbs})$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(1)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(1)\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs}$. GoosPitassi14
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(1)\) Amplitude estimation to additive $\delta$; at constant $\delta$, $O(1)$ queries. NayakWu99
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(1)\)· $\widetilde{\deg} \le 2\mathrm{Q} = O(1)$, and the Nayak-Wu counting bound is a degree bound. NayakWu99
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(1)\) putative Equal to $\mathrm{R}$: buying bias buys nothing here. See \(\mathrm{GapMaj}^{\delta}_{n}\). CKMPSS23
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(1)\) Sampling is non-adaptive.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(1)\) Every corner of the adaptive/noisy square costs $\Theta(1)$ here. BenDavidBlais20composition
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(1)\) $\bar{\mathrm{R}}_\varepsilon = \Theta(\mathrm{R}_\varepsilon)$ for every $f$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(1)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R}$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(1)\) putative Between $\mathrm{R}$ and $O(\mathrm{R})$: read each sampled coordinate $O(1)$ times and vote.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(1)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R})$.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(1)\)· $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R}$, and both ends are constant. BBGM22
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(1)\)· Between $\Omega(\sqrt{\mathrm{R}})$ and $\mathrm{LR}$. GLSS19
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$. Aaronson08
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(1)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(1)\) Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q})$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(1)\) putative Between $\mathrm{fbs}$ and $\mathrm{CG}^{\mathrm{pub}}$, both constant. CGLMSG23
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(1)\) putative Both players output the same uniformly random index; inputs of different value differ in $\ge n/2$ coordinates, so they win with probability $\ge 1/2$. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(1)\) All of $\mathrm{CG}^{\mathrm{ns}},\mathrm{CG}^{*},\mathrm{CG}^{\mathrm{pub}}$ collapse to $\Theta(\mathrm{CA})$. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(1)\) See $\mathrm{CG}^{*}$. CGLMSG23
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(1)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log\mathrm{Q})$.
\(\mathrm{sdeg}(f)\) Sign degree \(1\) $p(x) = \sum_i x_i - n/2$ has the right sign at every promise input. Against $\deg = \Theta(n)$: unbounded error trivialises gapped majority.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(1\) At $\delta \ge 1/8$ a degree-$1$ one-sided approximation exists, so $\mathrm{odeg}$ meets $\mathrm{sdeg}$ at the bottom.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(1)\) $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg} = O(1)$. Contrast the exact $\mathrm{rdeg} = \Theta(n)$: on partial functions the two versions of rational degree are unboundedly far apart.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(1)$. MahadevdeWolf15
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(1)\) $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
\(\chi(f)\) Conflict complexity \(O(1)\) $\chi \le \bar\chi$. The total-function bound $\chi = \Omega(\mathrm{bs})$ is false here.
\(\mathrm{RS}(f)\) Sabotage complexity \(O(1)\) $\mathrm{RS} = O(\bar\chi)$. Note $\mathrm{R} = O(\mathrm{RS}^2\log\mathrm{RS})$ is a total-function statement.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(O(1)\) $\mathrm{R}^{*} \le \mathrm{R}$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(1)\) Between $\widetilde{\deg}$ and $\mathrm{R}$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(1)\) $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(1)\) $\overline{\mathrm{prt}} \le \mathrm{prt}$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(O(\sqrt n)\) putative Uniform weights $w^x_i = (n/2)^{-1/2}$: two inputs of different value differ in $\ge n/2$ coordinates, so their weighted product is $\ge 1$, at total cost $\sqrt{2n}$. From below $\mathrm{EC} = \Omega(1)$ only, so this cell is not pinned -- but $O(\sqrt n)$ against $\mathrm{C} = \Theta(n)$ already refutes $\mathrm{EC} \le \mathrm{C}$-style tightness and, with $\mathrm{R}_0 = \Theta(n)$, refutes $\mathrm{R}_0 = O(\mathrm{EC}^2)$ on promises.

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

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

Separations it witnesses