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 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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{R}^{\mathrm{na}}(f_n) = O(1)\)from \(\mathrm{D}(f) = \Theta(n)\) against \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mu}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = \Theta(n)\) against \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}(f_n) = O(1)\)from \(\mathrm{C}(f) = \Theta(n)\) against \(\mathrm{bs}(f) = 1\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{fbs}(f_n) = O(1)\)from \(\mathrm{C}^0(f) = \Theta(n)\) against \(\mathrm{fbs}(f) = \Theta(1)\)
-
\(\mathrm{C}^1(f_n) \to \infty \ \text{ while } \ \mathrm{RC}(f_n) = O(1)\)from \(\mathrm{C}^1(f) = \Theta(n)\) against \(\mathrm{RC}(f) = \Theta(1)\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{FC}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = \Theta(n)\) against \(\mathrm{FC}(f) = \Theta(1)\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = \Theta(n)\) against \(\mathrm{R}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \bar{\mathrm{R}}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{RS}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = \Theta(n)\) against \(\mathrm{RS}(f) = O(1)\)
-
\(\mathrm{R}^{1}(f_n) \to \infty \ \text{ while } \ \chi(f_n) = O(1)\)from \(\mathrm{R}^{1}(f) = \Theta(n)\) against \(\chi(f) = O(1)\)
-
\(\mathrm{Q}_{\mathrm{E}}(f_n) \to \infty \ \text{ while } \ \bar{\chi}(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}(f) = \Theta(n)\) against \(\bar{\chi}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{0}(f_n) \to \infty \ \text{ while } \ \mathrm{LR}(f_n) = O(1)\)from \(\mathrm{Q}_{0}(f) = \Theta(n)\) against \(\mathrm{LR}(f) = \Theta(1)\)
-
\(\mathrm{NQ}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{NQ}(f) = \Theta(n)\) against \(\mathrm{bs}^0(f) = 1\)
-
\(\deg(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}^{\mathrm{na}}(f_n) = O(1)\)from \(\deg(f) = \Theta(n)\) against \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(1)\)
… and 358 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Unbounded: $\mathrm{D} = \Theta(n)$ against $\mathrm{R} = \Theta(1)$. The standard example, now readable by the derived layer.
-
Unbounded: certainty forces a full certificate, $\mathrm{R}_0 = \Theta(n)$, while $\mathrm{R} = \Theta(1)$.
-
Unbounded: $\mathrm{Q}_E = \Theta(n)$ against $\mathrm{Q} = \Theta(1)$. Same for $\mathrm{Q}_0$.
-
Unbounded: $\deg = \Theta(n)$ against $\widetilde{\deg} = \Theta(1)$, the promise gap being invisible to exact representation and free for approximate.
-
Unbounded: $\mathrm{rdeg} = \Theta(n)$ against $\mathrm{rdeg}_\varepsilon = O(1)$ -- and, since $\mathrm{rdeg} = \mathrm{PostQ}_{\mathrm{E}}$, exact and bounded-error post-selection are unboundedly far apart on promises.
-
Unbounded: $\mathrm{C} = \Theta(n)$ against $\mathrm{fbs} = \Theta(1)$; rounding a fractional certificate is a total-function argument.
-
Unbounded: $\mathrm{s} = 0$ identically while $\mathrm{bs} = 1$. Every measure above $\mathrm{s}$ is unbounded in terms of it on partial functions.
-
Unbounded: $\lambda = 0$ while $\deg = \Theta(n)$, since the sensitivity graph on the promise has no edges at all.