Q The Query Complexity Zoo
\(\mathrm{MAJ}_n\)

MAJORITY

Hard for quantum too ($\mathrm{Q}=\Theta(n)$), but with sensitivity only $\approx n/2$.

total basic arity: $n$ bits, $n$ odd— also: \mathrm{THR}_{n/2}

Description

$\mathrm{MAJ}_n(x)=1$ iff $|x| > n/2$.

Formal definition

$\mathrm{MAJ}_n(x) = \mathbb{1}[\,\sum_i x_i \ge (n+1)/2\,]$ for odd $n$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(n\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\)
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(n)\) Via Paturi: $\widetilde{\deg}(\mathrm{MAJ}) = \Theta(n)$ because the jump is at the middle layer. BBCMdW01 Paturi92
\(\deg(f)\) Exact degree \(n\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(n)\) Paturi92
\(\mathrm{sdeg}(f)\) Sign degree \(1\)
\(\mathrm{s}(f)\) Sensitivity \((n+1)/2\)
\(\mathrm{bs}(f)\) Block sensitivity \((n+1)/2\)
\(\mathrm{C}(f)\) Certificate complexity \((n+1)/2\)
\(\lambda(f)\) Spectral sensitivity \((n+1)/2\) The sensitivity graph is the middle-layer bipartite graph, which is $\tfrac{n+1}{2}$-regular, so $\lambda = \mathrm{s}$.
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(n)\) Symmetric functions have $\mathrm{rdeg} = \Omega(\deg)$. IJKKKSWW23
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(\sqrt{n})\)
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Between $\mathrm{R}=\Theta(n)$ and $\mathrm{D}=n$. (The saving from stopping early once one side reaches $(n+1)/2$ is only $\Theta(\sqrt n)$.)
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Same sandwich; expected cost cannot help by more than a constant at constant error.
\(\mathrm{s}^0(f)\) 0-sensitivity \((n+1)/2\) At a $0$-input with exactly $(n-1)/2$ ones, each of the $(n+1)/2$ zeros is sensitive.
\(\mathrm{s}^1(f)\) 1-sensitivity \((n+1)/2\)
\(\mathrm{bs}^0(f)\) 0-block sensitivity \((n+1)/2\)
\(\mathrm{bs}^1(f)\) 1-block sensitivity \((n+1)/2\)
\(\mathrm{C}^0(f)\) 0-certificate complexity \((n+1)/2\)
\(\mathrm{C}^1(f)\) 1-certificate complexity \((n+1)/2\)
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \((n+1)/2\) Every input needs a full majority-sized certificate, so the min and the max coincide.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \((n+1)/2\) Squeezed: $\mathrm{bs}\le\mathrm{fbs}\le\mathrm{C}$ and both ends are $(n+1)/2$. The certificate LP is integral for MAJ. Aaronson08
\(\mathrm{FC}(f)\) Fractional certificate complexity \((n+1)/2\) Equal to $\mathrm{fbs}$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \((n+1)/2\) Same squeeze, since $\mathrm{fbs}\le\mathrm{EC}\le\mathrm{C}$. GJKKLSSV17
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) $\mathrm{RC}=\Theta(\mathrm{fbs})=\Theta(n)$. Aaronson08
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) The classical adversary equals $\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}=\Theta(\sqrt{\mathrm{RC}})$. Verifying a majority is quadratically cheaper than computing it. Aaronson08
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) At least $\deg/2 = n/2$ and at most $n$; [AmbainisGruslysEtAl16] pin down the exact quantum complexity of threshold functions. BBCMdW01 AmbainisGruslysEtAl16
\(\mathrm{ndeg}(f)\) Nondeterministic degree \((n+1)/2\) putative Exactly. Upper: $\prod_{j=0}^{(n-1)/2}(|x|-j)$ vanishes exactly on the $0$-inputs. Lower: $\mathrm{MAJ}_n = \mathrm{THR}^n_{(n+1)/2}$, and restricting $(n-1)/2$ variables to $0$ leaves $\wedge_{(n+1)/2}$, whose nondeterministic degree is $(n+1)/2$ (the \(\mathrm{AND}_n\) line); $\mathrm{ndeg}$ cannot increase under restriction. This is the \(\mathrm{THR}^n_k\) value $\mathrm{ndeg} = k$ at $k = (n+1)/2$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(\sqrt n)\) putative Sharply below $\widetilde{\deg}(\mathrm{MAJ})=\Theta(n)$. A Chebyshev polynomial scaled to be $\le 1/3$ in absolute value on $\{0,\dots,(n-1)/2\}$ has grown past $2/3$ one step later, and nothing constrains it above; the matching $\Omega(\sqrt n)$ is the Markov-brothers bound on an interval with $\Theta(n)$ points.
\(\mathrm{rank}(f)\) Decision tree rank \((n+1)/2\) putative Prover-Delayer: until one side has $(n+1)/2$ votes the Delayer may answer either way, scoring a point each time; the counting tree attains it.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Every variable is relevant.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) In fact $n - O(1)$, which is sharper than the recorded $\Theta(n)$ but mixes an exact and an asymptotic term, so it lives here rather than in the value. If two coordinates go unqueried the remaining $n-2$ bits can be set to split evenly, and then the two unread bits decide the answer, leaving it a fair coin flip; so every non-adaptive query set must miss at most one coordinate and $\mathrm{R}^{\mathrm{na}} \ge n-1$. The matching $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = n$ is trivial.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) At most $\mathrm{R}=\Theta(n)$; and the sabotaged input with $(n-1)/2$ ones, $(n-1)/2$ zeros and a single $\ast$ hides that $\ast$ among $n$ positions. BenDavidKothari18
\(\mathrm{MaxInf}(f)\) Maximum influence \(\binom{n-1}{(n-1)/2}2^{1-n} = \Theta(1/\sqrt n)\) Every coordinate is pivotal exactly when the other $n-1$ split evenly. ODonnell14
\(\mathrm{Var}(f)\) Variance \(1\) Balanced for odd $n$.
\(\mathrm{osss}(f)\) OSSS number \(2^{n-1}/\binom{n-1}{(n-1)/2} = \sqrt{\pi n/2}\,(1+o(1))\) putative $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = \binom{n-1}{(n-1)/2}2^{1-n}$. The largest value OSSS attains among the standard symmetric functions, and still only $\Theta(\sqrt n)$ against $\mathrm{D} = n$.
\(\mathrm{nsr}(f)\) Noise robustness \(4+2\sqrt2 + o(1) = \Theta(1)\) putative In the $n\to\infty$ limit $\mathrm{NS}_\delta = \tfrac1\pi\arccos(1-2\delta)$, which reaches $\mathrm{Var}/4 = \tfrac14$ at $1-2\delta = \cos(\pi/4)$, i.e. $\delta^{*} = \tfrac12(1-1/\sqrt2) \approx 0.1464$. Majority is noise-sensitive at constant rate even though it is the most stable low-influence function -- the two statements live at different scales.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(\sqrt n)\) Boolean-valued, so equal to $\mathrm{I}(f)$.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\Theta(\sqrt\delta)\) As $n\to\infty$, $\mathrm{NS}_\delta \to \tfrac1\pi\arccos(1-2\delta)$. Majority is the most noise-stable of all low-influence functions (Majority Is Stablest). ODonnell14
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(\tfrac{2}{\pi}\arcsin\rho + o(1)\) Sheppard formula, in the $n\to\infty$ limit. ODonnell14
\(\mathrm{spar}(f)\) Fourier sparsity \(2^{n-1}\) MAJ is odd, so only odd-size sets can appear, and the standard formula for $\widehat{\mathrm{MAJ}}(S)$ is nonzero for every one of them. ODonnell14
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(n\) The support contains every singleton (odd sets of size $1$ have nonzero coefficient), so it spans $\mathbb{F}_2^n$.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(n - \mathrm{B}(n) + 1\) Exactly, where $\mathrm{B}(n)$ is the number of ones in the binary expansion of $n$. Lower bound from granularity: every Fourier coefficient of $\mathrm{MAJ}_n$ is an integer multiple of $2^{-k}$ with $k = n - \mathrm{B}(n)$, and [ChistopolskayaPodolskii18] show $\mathrm{D}^{\oplus} \ge k+1$. Parity queries buy $\mathrm{B}(n)-1$ queries off $\mathrm{D} = n$, and no more. ChistopolskayaPodolskii18
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{RC}(f)$, with both ends $\Theta(n)$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(n)\) $\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)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(n)\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$ and $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_\varepsilon)$, so the multiplicative adversary is $\Theta(\mathrm{Q})$ on every function; here $\mathrm{Q} = \Theta(n)$. Spalek08
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{RS}(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with $\mathrm{RS}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\mathrm{RS}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with $\mathrm{RS}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(n^2)\) Sandwiched between $\mathrm{Adv}^2 = \Theta(n^2)$ and $\mathrm{C}^0\mathrm{C}^1 = \Theta(n^2)$ [CGLMSG23]. Like \(\oplus_n\) this sits above the arity: the sensitivity graph of majority is biregular of degree $\Theta(n)$ between the two middle layers, so $\lambda = \Theta(n)$ and the distance-$1$ game alone already costs $\Theta(n^2)$. CGLMSG23
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\Theta(\log n)\) Newman's degree-$O(\log(1/\varepsilon))$ rational approximation to $|x|$, rescaled to the slices $k = 0,\dots,n$, approximates the sign of $k - n/2$ with degree $O(\log n)$; the matching $\Omega(\log n)$ is in [MahadevdeWolf15]. Compare $\widetilde{\deg}(\mathrm{MAJ}) = \Theta(n)$: rational approximation is exponentially cheaper than polynomial approximation here, which is exactly what makes majority the canonical postselection example. Newman64 MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(\log n)\) Aaronson gave the first postselected majority algorithm; Mahadev-de Wolf made it optimal and observed that reading the algorithm backwards reproves Newman's theorem. MahadevdeWolf15 Aaronson05postbqp
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(n)\) Sandwiched between $\mathrm{Q} = \Theta(n)$ and the universal $O(n)$ upper bound. BNRdW05
\(\deg_2(f)\) Mod-2 degree \((n+1)/2\) putative Recorded along the subfamily $n = 2^m - 1$. The $p=2$ case of the $\deg_p$ line below. The restriction to $n = 2^m-1$ is only for tidiness: running the same Lucas computation for every $n$ gives $\deg_2(\mathrm{MAJ}_n) = 2^{\lfloor \log_2 n\rfloor}$, so $\deg_2$ is always a power of two: it equals $n$ exactly when $n$ is one, and bottoms out at $(n+1)/2$ at $n = 2^m-1$, which is the case recorded here. Either way $\deg_2 = \Theta(n)$ while $\deg = n$ -- unlike \(\mathrm{IP}_n\), majority gets essentially no discount from characteristic $2$.
\(\deg_p(f)\) Mod-p degree \((n+1)/2 \text{ for } p = 2,\ n = 2^m - 1\) The $\mathbb{F}_2$ multilinear expansion of the threshold $\mathrm{Th}_k^n$ is $\sum_{|S| \ge k} \binom{|S|-1}{k-1}\prod_{i \in S} x_i$. By Lucas' theorem $\binom{s-1}{k-1}$ is odd iff the binary digits of $k-1$ are a submask of those of $s-1$; with $n = 2^m-1$ and $k = 2^{m-1}$ the only $s-1 \le n-1$ containing the mask $0\underbrace{1\cdots1}_{m-1}$ is $2^{m-1}-1$ itself, so the degree is exactly $2^{m-1} = (n+1)/2$. For $n = 3$ this is the familiar $\mathrm{MAJ}_3 = xy + yz + zx$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. Li18
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = (n+1)/2$ and $\mathrm{Adv}^{\pm}(f) = \Theta(n)$ here. The positive-weight adversary is already tight for majority, unlike for \(\mathrm{AND}_n \circ \mathrm{OR}_n\)-style functions where the certificate barrier bites.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = (n+1)/2$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{C}_{\min}(f) \le \mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, with $\mathrm{C}_{\min}(f) = (n+1)/2$ and $\mathrm{UC}(f) = \Theta(n)$ here.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = (n+1)/2$ and $\mathrm{D}(f) = n$ here. Majority cannot separate any of the certificate-flavoured measures from $\mathrm{D}$ by more than a factor of two.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) putative The uniform distribution is already a product distribution and already hard: after $m$ queries the unseen weight is $\mathrm{Bin}(n-m,\tfrac12)$, whose standard deviation $\tfrac12\sqrt{n-m}$ exceeds the distance to the threshold with constant probability unless $n - m = O(1)$. Unlike \(\mathrm{Tribes}_{w,s}\) or \(\mathrm{ADDR}_k\), majority needs no correlated distribution to be hard.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(n\log n)\)· putative Upper: $O(\mathrm{R}\log \mathrm{R})$ by repeating each query $O(\log n)$ times. Lower: on inputs of weight $(n\pm1)/2$ the answer is determined by a margin of one bit, so an estimator of the weight must have error variance $o(1)$; a coordinate read $k$ times still has posterior error probability $2^{-\Theta(k)}$, contributing $\Theta(n2^{-\Theta(k)})$ to the variance of the estimated weight, which forces $k = \Omega(\log n)$ on a constant fraction of the coordinates. So noisy majority is a second natural $\Theta(n\log n)$ family alongside \(\oplus_n\) -- and the $\Omega(\mathrm{I}\log\mathrm{I})$ bound of [GLX26noisy] only gives $\Omega(\sqrt n\log n)$ here, so it is not the binding constraint. FRPU94
\(\mathrm{DTsize}(f)\) Decision tree size \(O\!\big(2^n/\sqrt n\big)\) putative The counting tree -- query until one side reaches $(n+1)/2$ -- has exactly $\binom{n+1}{(n+1)/2}$ leaves, since the stopping sequences of each type number $\sum_{j<m}\binom{m+j-1}{j} = \tfrac12\binom{2m}{m}$ with $m=(n+1)/2$. That is $6$ for $\mathrm{MAJ}_3$, matching the familiar three-query tree. Recorded as an upper bound only: no matching lower bound is claimed here, the best easy one being $2^{(n+1)/2}$ from the fact that every leaf subcube has codimension $\ge (n+1)/2$.
\(\hat{L}_1(f)\) Spectral norm \(\Theta\!\big(2^{n/2}/\sqrt n\big)\) putative Exponentially large, in sharp contrast with $\hat L_1(\mathrm{OR}_n) < 3$. Upper: Cauchy-Schwarz against $\mathrm{spar} = 2^{n-1}$ gives $\hat L_1 \le 2^{(n-1)/2}$. The exact sum $\sum_{k \text{ odd}}\binom nk \big|\widehat{\mathrm{MAJ}}([k])\big|$, evaluated from the standard closed form for $\widehat{\mathrm{MAJ}}(S)$, is $\tfrac{2}{\sqrt\pi}\,2^{n/2}n^{-1/2}(1+o(1))$ -- so majority is within a $\sqrt n$ factor of the largest spectral norm any $n$-bit function can have. ODonnell14
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$, and the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform product distribution already attains it: after $o(n)$ queries the unseen coordinates leave the majority undecided with constant probability. Yao77
\(\mathrm{cbs}(S)\) Critical block sensitivity \((n+1)/2\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $(n+1)/2$ at a balanced input. GoosPitassi14
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\lceil (n+1)/4 \rceil\) Exactly, from $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf00] and the $\mathrm{ndeg} = (n+1)/2$ recorded above. Nondeterminism buys only a factor $2$ over $\mathrm{Q} = \Theta(n)$ here, unlike at \(\mathrm{OR}_n\) where $\mathrm{NQ} = 1$. deWolf00
\(\mathrm{QS}_{\mathrm{weak}}(f)\) Weak quantum sabotage complexity \(\Theta(\sqrt n)\) CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24
\(\mathrm{QS}_{\mathrm{str}}(f)\) Strong quantum sabotage complexity \(\Theta(\sqrt n)\) CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) Weak quantum sabotage index complexity \(\Theta(\sqrt n)\) CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) Strong quantum sabotage index complexity \(\Theta(\sqrt n)\) CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) Exact quantum certification complexity \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) Zero-error quantum certification complexity \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
\(\overline{\deg}(f)\) Exact bounded polynomial degree \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) One-sided-error bounded polynomial degree \(\Theta(n)\) The certification/polynomial bounds are squeezed between rational degree Θ(n) and certificate complexity O(n); bdeg=deg for total functions. [KLLPV26, Lemma 50, Theorems 5 and 9]. KLLPV26
\(\lambda^{\mathrm{cert}}(f)\) Spectral sensitivity certification \(\sqrt{(n+1)/2}\) Theorem 42: λcert=√s, with s=(n+1)/2. KLLPV26
\(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) Bounded polynomial degree with error on 0-inputs \(\Theta(n)\) Both bounded one-sided polynomials are approximate polynomials, so approximate degree Θ(n) is a floor; exact degree n is a ceiling. KLLPV26
\(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) Bounded polynomial degree with error on 1-inputs \(\Theta(n)\) Both bounded one-sided polynomials are approximate polynomials, so approximate degree Θ(n) is a floor; exact degree n is a ceiling. KLLPV26
\(\mathrm{R}_{\mathrm{RP}}(f)\) One-sided randomized queries with certain rejection \(\Theta(n)\) The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26

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

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

Cited as a witness by