\(\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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{nsr}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{nsr}(f) = 4+2\sqrt2 + o(1) = \Theta(1)\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = (n+1)/2\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\mathrm{RC}(f_n) \to \infty \ \text{ while } \ \mathrm{Var}(f_n) = O(1)\)from \(\mathrm{RC}(f) = \Theta(n)\) against \(\mathrm{Var}(f) = 1\)
-
\(\mathrm{osss}(f_n) = 2^{\Omega(\mathrm{PostQ}_{\varepsilon}(f_n))}\)from \(\mathrm{osss}(f) = 2^{n-1}/\binom{n-1}{(n-1)/2} = \sqrt{\pi n/2}\,(1+o(1))\) against \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\log n)\)
-
\(\hat{L}_1(f_n) = 2^{\Omega(\mathrm{s}^0(f_n))}\)from \(\hat{L}_1(f) = \Theta\!\big(2^{n/2}/\sqrt n\big)\) against \(\mathrm{s}^0(f) = (n+1)/2\)
-
\(\mathrm{spar}(f_n) = 2^{\Omega(\mathrm{UC}_{\min}(f_n))}\)from \(\mathrm{spar}(f) = 2^{n-1}\) against \(\mathrm{UC}_{\min}(f) = \Theta(n)\)
-
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_n) = \Omega\big(\mathrm{I}(f_n)^{2}\big)\)from \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f) = \Theta(n)\) against \(\mathrm{I}(f) = \Theta(\sqrt{n})\)
-
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f_n) = \Omega\big(\mathrm{I}^{1}(f_n)^{2}\big)\)from \(\mathrm{Q}_{0}^{\mathrm{cert}}(f) = \Theta(n)\) against \(\mathrm{I}^{1}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{s}(f_n) \to \infty \ \text{ while } \ \mathrm{nsr}(f_n) = O(1)\)from \(\mathrm{s}(f) = (n+1)/2\) against \(\mathrm{nsr}(f) = 4+2\sqrt2 + o(1) = \Theta(1)\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = \Theta(n)\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\deg_2(f_n) \to \infty \ \text{ while } \ \mathrm{Var}(f_n) = O(1)\)from \(\deg_2(f) = (n+1)/2\) against \(\mathrm{Var}(f) = 1\)
-
\(\mathrm{osss}(f_n) = 2^{\Omega(\mathrm{rdeg}_{\varepsilon}(f_n))}\)from \(\mathrm{osss}(f) = 2^{n-1}/\binom{n-1}{(n-1)/2} = \sqrt{\pi n/2}\,(1+o(1))\) against \(\mathrm{rdeg}_{\varepsilon}(f) = \Theta(\log n)\)
-
\(\hat{L}_1(f_n) = 2^{\Omega(\mathrm{UC}(f_n))}\)from \(\hat{L}_1(f) = \Theta\!\big(2^{n/2}/\sqrt n\big)\) against \(\mathrm{UC}(f) = \Theta(n)\)
-
\(\mathrm{spar}(f_n) = 2^{\Omega(\mathrm{cjdeg}_{\varepsilon}(f_n))}\)from \(\mathrm{spar}(f) = 2^{n-1}\) against \(\mathrm{cjdeg}_{\varepsilon}(f) = \Theta(n)\)
… 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
-
\(\mathrm{D}(\mathrm{MAJ}_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{s}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{s}^0(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{s}^1(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{bs}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{fbs}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{C}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{C}^0(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{C}^1(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{C}_{\min}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{RC}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{EC}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{FC}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{bs}^0(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{bs}^1(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{rank}(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{D}^{\mathrm{na}}(\mathrm{MAJ}_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{R}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{R}_{0}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{R}^{1}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{RS}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\bar{\chi}(g)(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{LR}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{noisyR}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{R}^{*}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{CA}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{CG}(\mathrm{MAJ}_n) = \Theta(n^2) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{CG}^{\mathrm{pub}}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{CG}^{*}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{CG}^{\mathrm{ns}}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{R}^{\mathrm{na}}(\mathrm{MAJ}_n) = n - O(1) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{Q}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{Q}_{\mathrm{E}}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{Q}_{0}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{PostQ}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(\log n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{QC}(\mathrm{MAJ}_n) = \Theta(\sqrt n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{Q}^{\mathrm{rob}}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{Adv}^{\pm}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\gamma_2^{\alpha}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{MAdv}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\lambda(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\deg(\mathrm{MAJ}_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\widetilde{\deg}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{rdeg}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{rdeg}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(\log n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{ndeg}(\mathrm{MAJ}_n) = \le (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\deg_2(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{NS}_{\delta}(\mathrm{MAJ}_n) \to \tfrac12 - \tfrac1\pi\arcsin(1-2\delta) > 0\)
-
\(\deg_2(\mathrm{MAJ}_n) = (n+1)/2 \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{cjdeg}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\widetilde{\deg}_{+}(\mathrm{MAJ}_n) = \Theta(\sqrt n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{I}(\mathrm{MAJ}_n) = \Theta(\sqrt{n}) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{I}^{1}(\mathrm{MAJ}_n) = \Theta(\sqrt n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{spar}(\mathrm{MAJ}_n) = 2^{n-1} \to \infty, \qquad \mathrm{NS}_{\delta}(\mathrm{MAJ}_n) \to \tfrac12 - \tfrac1\pi\arcsin(1-2\delta) > 0\)
-
\(\mathrm{spar}(\mathrm{MAJ}_n) = 2^{n-1} \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\dim_{\mathbb{F}_2}(\mathrm{MAJ}_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\mathrm{MAJ}_n) \to \tfrac12 - \tfrac1\pi\arcsin(1-2\delta) > 0\)
-
\(\dim_{\mathbb{F}_2}(\mathrm{MAJ}_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\mathrm{prt}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) vs \(\mathrm{Stab}_{\rho}(f)\) total No bound exists open →\(\overline{\mathrm{prt}}_{\varepsilon}(\mathrm{MAJ}_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\mathrm{MAJ}_n) \to \tfrac{2}{\pi}\arcsin\rho > 0\)