Q The Query Complexity Zoo
\(\mathrm{MAJ}_3^{\circ d}\)

Recursive MAJORITY-of-3

The other classical recursive benchmark; its randomized complexity is still not pinned down.

total composed arity: $N = 3^d$ bits— also: iterated 3-majority, 3-MAJ tree

Description

The depth-$d$ ternary tree all of whose gates are $\mathrm{MAJ}_3$.

Formal definition

$f_0(x)=x$, $f_k(x^{(1)},x^{(2)},x^{(3)}) = \mathrm{MAJ}_3\big(f_{k-1}(x^{(1)}),f_{k-1}(x^{(2)}),f_{k-1}(x^{(3)})\big)$, $f=f_d$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(N = 3^d\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) In terms of $N = 3^d$ that is between $N^{0.8663}$ and $N^{0.8869}$; the exact exponent is a well-known open problem. History of the lower bound: $(7/3)^d$ [JayramKumarSivakumar03] $\to 2.55^d$ [Leonardos13] $\to 2.57143^d$ [MNSSTX16] $\to 2.59^d$ [GoosJayram16], the last via \(\mathrm{cjdeg}_{\varepsilon}(f)\) rather than information complexity. The upper bound is the interleaved recursive algorithm of [MNSSTX16, Thm 4.2] and is zero-error, so it bounds $\mathrm{R}_0$ too. GoosJayram16 MNSSTX16 Leonardos13 JayramKumarSivakumar03
\(\deg(f)\) Exact degree \(N\)
\(\mathrm{s}(f)\) Sensitivity \(2^d = N^{0.6309}\)
\(\mathrm{bs}(f)\) Block sensitivity \(2^d\)
\(\mathrm{C}(f)\) Certificate complexity \(2^d\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(2^d\) Between $\mathrm{bs}=2^d$ and $\mathrm{C}=2^d$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(2^d\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(2^d\) Between $\mathrm{fbs}$ and $\mathrm{C}$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N = 3^d\)
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \((N+1)/2 = (3^d+1)/2\) Exactly. The granularity of $\mathrm{MAJ}_3^{\circ d}$ is $2^{-(N-1)/2}$, and [ChistopolskayaPodolskii18] show $\mathrm{D}^{\oplus}\ge k+1$ for granularity $2^{-k}$; the matching parity decision tree is explicit. So parity queries halve the cost here, unlike on \(\oplus_n\) (where they collapse it) or \(\mathrm{IP}_n\) (where they buy a factor $2$ at most). ChistopolskayaPodolskii18
\(\lambda(f)\) Spectral sensitivity \(2^d = N^{\log_3 2}\) $\lambda(\mathrm{MAJ}_3)=2$, multiplicativity.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(2^d)\) $\mathrm{Adv}^{\pm}(\mathrm{MAJ}_3)=2$ and $\mathrm{Adv}^\pm$ composes perfectly, so $\mathrm{Q} = \Theta(\mathrm{Adv}^\pm(\mathrm{MAJ}_3)^d)$. Reichardt11
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(2^d)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{C}(f)$, with both ends $2^d$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(2^d)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = 2^d$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(2^d)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = 2^d$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(2^d)\) 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(2^d)\) 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{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(2^d)\) $\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(2^d)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(2^d)\) $\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(2^d)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(2^d)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(2^d)$ here.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(2.59^{\,d}),\ O(2.64944^{\,d})\) The Goos-Jayram conical junta bound $\Omega(2.59^d)$ is, as of writing, also the best known lower bound on $\mathrm{R}$ itself -- the nonnegative LP is where all recent progress on recursive majority has come from. Upper bound inherited from $\mathrm{cjdeg} \le \mathrm{R}$. GoosJayram16 MNSSTX16
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\alpha^{d},\ \alpha \in [2.59,\ 2.64944]\) As for \(\bar{\wedge}\text{-tree}\), self-composition makes $\mathrm{R}^{*}$ the exact base of the exponential; pinning $\alpha$ is the open problem on recursive majority. GoosJayram16 MNSSTX16
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\ge (\tfrac12 - \delta)\,2.57143^{\,d}\) The lower bound is proved against an explicit hard distribution, so it is a statement about $\mathrm{D}^{\mu}_{\delta}$; Yao's principle then transfers it to $\mathrm{R}_\delta$. Goos-Jayram's later $\Omega(2.59^d)$ goes through conical juntas instead and is not of this form. MNSSTX16
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) Identical to the bounds on $\mathrm{R}$: the interleaved algorithm of [MNSSTX16, Thm 4.2] that gives the upper bound is zero-error, and the lower bound applies a fortiori. So recursive majority is one of the functions where zero error is known to be free. GoosJayram16 MNSSTX16
\(\mathrm{s}^0(f)\) 0-sensitivity \(2^d\) putative Take the input in which every gate sees exactly two $0$-children; those two children are the sensitive ones, so the sensitive leaves double at each level. $\mathrm{MAJ}_3$ is self-dual, so the same works on the $1$-side.
\(\mathrm{s}^1(f)\) 1-sensitivity \(2^d\) putative As $\mathrm{s}^0$, by self-duality of $\mathrm{MAJ}_3$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(2^d\) Between $\mathrm{s}^0 = 2^d$ and $\mathrm{bs} = 2^d$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(2^d\) Between $\mathrm{s}^1 = 2^d$ and $\mathrm{bs} = 2^d$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(2^d\) Between $\mathrm{bs}^0 = 2^d$ and $\mathrm{C} = 2^d$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(2^d\) Between $\mathrm{bs}^1 = 2^d$ and $\mathrm{C} = 2^d$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(2^d\) putative Every input of $\mathrm{MAJ}_3$ costs exactly $2$ to certify, so certificate complexity is the same at every input at every level: $\mathrm{C}_{\min} = \mathrm{C} = 2^d$. Recursive majority is perfectly homogeneous in this respect, unlike \(K^{\circ k}\) ($\mathrm{C}_{\min} = \mathrm{C}^{0.77}$).
\(\deg_2(f)\) Mod-2 degree \(2^d = N^{0.6309}\) putative Over $\mathbb{F}_2$, $\mathrm{MAJ}_3 = xy+xz+yz$ has degree $2$, and mod-$2$ degree is exactly multiplicative under composition (the top-degree monomials of the outer function live on disjoint blocks, so their expansions cannot cancel). So $\deg_2 = 2^d = \mathrm{s}$, quadratically below $\deg = N$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(N = 3^d\) putative An unambiguous $1$-certificate family of width $w$ writes $f$ as a sum of $\le w$-variable conjunctions with no cancellation, so $\deg(f) \le \mathrm{UC}(f)$. Every read-once formula has $\deg = N$, which forces $\mathrm{UC} = \mathrm{SP} = \mathrm{D} = N$ -- even though $\mathrm{C} = N^{0.63}$. Verified by exact set-partition search at $d = 1,2$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(N = 3^d\) Between $\mathrm{UC} = N$ and $\mathrm{D} = N$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(N)\) Between $\deg/2 = N/2$ and $\mathrm{D} = N$. Exactness costs the full $N$ against $\mathrm{Q} = \Theta(N^{0.63})$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(2^d),\ O(2.65^{\,d})\) As on \(\bar{\wedge}\text{-tree}\), $\deg/2$ is a floor for $\mathrm{Q}_{\mathrm{E}}$ and not for $\mathrm{Q}_0$. Lower: $\mathrm{Q} = \Theta(2^d)$, which beats the $\mathrm{rdeg}/2 = \Omega(1.732^{\,d})$ polynomial floor. Upper: $\mathrm{Q}_0 \le 2\mathrm{R}_0 = O(2.64944^{\,d})$, well below $\mathrm{D} = 3^d$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(2^d)\) Sandwiched: $\lambda(f) = O(\widetilde{\deg}(f))$ (the step [ABKRT21] combine with Huang to get $\deg = O(\widetilde{\deg}^2)$) and $\widetilde{\deg}(f) \le 2\mathrm{Q}(f)$, with $\lambda = 2^d$ and $\mathrm{Q} = \Theta(2^d)$ here. So $\widetilde{\deg}$ sits with $\mathrm{Q}$ and $\lambda$ at $N^{0.63}$, quadratically below $\deg = N$. ABKRT21
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(N)\) putative Between $N/3$ and $N$. Upper: $\mathrm{rank}\le\mathrm{D}$. Lower, by a Prover--Delayer argument that composes: $\mathrm{rank}(f\circ g^n) \ge \mathrm{D}(f)\,(\mathrm{C}_{\min}(g)-1)$. Indeed the Delayer defers the first $\mathrm{C}_{\min}(g)-1$ queries inside each block -- so few bits can never determine that block's value -- and only then commits to the value the block will take, answering afterwards so as to force it. The order in which blocks reach that commitment is an adversary play against $f$, and the game cannot end until the completed blocks alone determine $f$, so at least $\mathrm{D}(f)$ blocks reach commitment, each paying $\mathrm{C}_{\min}(g)-1$ points. With $f = \mathrm{MAJ}_3^{\circ(d-1)}$ and $g = \mathrm{MAJ}_3$ ($\mathrm{D}(f) = 3^{d-1}$, $\mathrm{C}_{\min}(g) = 2$) this gives $\mathrm{rank} \ge 3^{d-1} = N/3$. Exact minimisation gives $2, 5, 14$ at $d = 1,2,3$, i.e. $(3^d+1)/2$. Recursive majority therefore has essentially full rank, while $\mathrm{C}_{\min} = N^{0.63}$ -- the generic $\mathrm{C}_{\min}\le\mathrm{rank}$ bound is far from tight here.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(N)}\) putative A rank-$r$ decision tree contains a complete binary branching of depth $r$, hence has $\ge 2^r$ leaves; with $\mathrm{rank} = \Omega(N)$ that gives $2^{\Omega(N)}$, and $2^{\mathrm{D}} = 2^N$ is the ceiling. Exact minimisation gives $6$ leaves at $d=1$ and $116$ at $d=2$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(N = 3^d\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = N$, so both unambiguous sides cost the full $N$ against $\mathrm{C} = \mathrm{C}_{\min} = N^{0.63}$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(2^d)\) Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = 2^d$ and $\mathrm{Q} = \Theta(2^d)$ here. The positive-weight adversary is therefore already optimal on recursive majority.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(4^{\,d}) = \Theta(N^{1.2619})\) putative Pinned, and far above the arity $N = 3^d$: the private-coin certificate game is not capped by $\mathrm{D}$. Lower: $\mathrm{CG} \ge \mathrm{Adv}^2 = (2^d)^2$. Upper: $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = 2^d\cdot 2^d$. The two meet exactly, so $\mathrm{MAJ}_3^{\circ d}$ is a clean witness for $\mathrm{CG} = \Theta(\mathrm{D}^{1.26})$ -- and for the fact that $\mathrm{CG}$ can exceed $n$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(2^{d/2}) = \Theta(N^{0.3155})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = 2^d$ here.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$, and this is the recorded \(\mathrm{R}_{\varepsilon}(f)\) window verbatim.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) Between $\mathrm{R}_{\varepsilon}$ and $\mathrm{R}_0$, whose recorded windows coincide here (the [MNSSTX16] algorithm is zero-error).
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) Between $\mathrm{R}_{\varepsilon}$ and $\mathrm{R}_0$, whose recorded windows coincide here.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) putative Not pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(2^d)$ -- star out a uniformly random one of the $\mathrm{bs}$ disjoint sensitive blocks of a maximally block-sensitive input; all other bits agree with it, so finding a $\ast$ is unstructured search over the blocks. Sabotage complexity composes perfectly, so pinning $\mathrm{RS}$ here would immediately pin the \(\mathrm{R}^{*}(f)\) exponent.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) Sandwiched: $\mathrm{fbs} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\mathrm{fbs} = 2^d$ and the recorded $\mathrm{R}$ upper bound. The related conical-junta LP \(\mathrm{cjdeg}_{\varepsilon}(f)\) is known to be $\Omega(2.59^d)$, i.e. near the top of this window.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\)· As \(\mathrm{prt}_{\varepsilon}(f)\); the relaxed partition bound still dominates $\mathrm{fbs}$ (the zoo's own observation about the [JainKlauck10] techniques) and is still at most $\mathrm{R}$.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(N = 3^d\) putative The Fourier support contains every singleton: $\widehat{\mathrm{MAJ}_3}$ is supported on $\{1\},\{2\},\{3\},\{123\}$, and taking the outer set $A = \{j\}$ at every level embeds each lower-level support set into a block, so by induction $\{\ell\} \in \mathrm{supp}\widehat{f}$ for every leaf $\ell$. Singletons alone span $\mathbb{F}_2^N$, so $\dim_{\mathbb{F}_2} = N$ and the bound $\mathrm{D}^{\oplus}\le\dim_{\mathbb{F}_2}$ is vacuous -- the real bound on \(\mathrm{D}^{\oplus}(f)\) here is the granularity one, which gives $(N+1)/2$.
\(\mathrm{I}^{1}(f)\) Total L1 influence \((3/2)^d = N^{0.3691}\) putative For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; they differ only for bounded real-valued $p$. See \(\mathrm{I}(f)\).
\(\mathrm{MaxInf}(f)\) Maximum influence \(2^{-d} = N^{-0.6309}\) putative Recursive majority is transitive, so every coordinate has the same influence $\mathrm{I}(f)/N = (3/2)^d/3^d = 2^{-d}$. Note this is exactly $1/\mathrm{s}$: the maximum influence is the reciprocal of the sensitivity.
\(\mathrm{Var}(f)\) Variance \(1\) $\mathrm{MAJ}_3$ is balanced, so every level is, and $\hat f(\emptyset) = 0$.
\(\mathrm{osss}(f)\) OSSS number \(2^d = N^{0.6309}\) putative $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = 2^{-d}$. Exactly $\mathrm{s}(f) = 2^d$: for a transitive balanced function $\mathrm{osss} = N/\mathrm{I}$, and here that is the sensitivity on the nose. Still short of $\mathrm{R}_0 = \Omega(2.59^d)$.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta((3/2)^d) = \Theta(N^{0.3691})\) putative Near $\rho = 1$ the stability recursion $\Psi(\rho) = (3\rho+\rho^3)/4$ of the \(\mathrm{NS}_{\delta}(f)\) entry acts as $1-\varepsilon \mapsto 1-\tfrac32\varepsilon$, so starting from $\varepsilon = 2\delta$ the stability leaves the neighbourhood of $1$ after $(3/2)^d\delta = \Theta(1)$, i.e. $\delta^{*} = \Theta((2/3)^d)$. Equal to $\mathrm{I}(f) = (3/2)^d$, so the bound $\mathrm{nsr}\le 4\mathrm{I}/\mathrm{Var}$ is tight and $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(N)$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \((3/2)^d = N^{0.3691}\) putative $\mathrm{MAJ}_3$ is balanced, so on a uniform input the three subtree values are uniform and independent and total influence multiplies: $\mathrm{I}(f\circ g^n) = \mathrm{I}(f)\mathrm{I}(g)$. Each coordinate of $\mathrm{MAJ}_3$ is pivotal exactly when the other two disagree, so $\mathrm{I}(\mathrm{MAJ}_3)=\tfrac32$.
\(\hat{L}_1(f)\) Spectral norm \(2^{\Theta(N)}\) putative Balancedness kills the empty coefficient, so Fourier coefficients of the composition factor exactly and $\widehat L_1(f\circ g^n) = \sum_A |\widehat f(A)|\,\widehat L_1(g)^{|A|}$. With $\widehat{\mathrm{MAJ}_3} = \tfrac12(\chi_1+\chi_2+\chi_3-\chi_{123})$ this reads $\widehat L_1(d) = \tfrac32 \widehat L_1(d-1) + \tfrac12 \widehat L_1(d-1)^3$, starting from $2$; the cubic recursion gives $\log_2 \widehat L_1 \sim 0.26\,N$, against the universal ceiling $2^{N/2}$. (Values: $2, 7, 182, 3014557,\dots$)
\(\mathrm{spar}(f)\) Fourier sparsity \(2^{\Theta(N)}\) putative The same factorisation as for \(\hat{L}_1(f)\), now counting terms instead of adding them: $\mathrm{spar}(f\circ g^n) = \sum_{A \in \mathrm{supp}\widehat f} \mathrm{spar}(g)^{|A|}$, since every Fourier coefficient of the composition is a single product and nothing cancels. Here $\mathrm{spar}(d) = 3\,\mathrm{spar}(d-1) + \mathrm{spar}(d-1)^3$ from $\mathrm{spar}(0)=1$: $4, 76, 439204, \dots$, so $\log_2\mathrm{spar} = \Theta(3^{\,d}) = \Theta(N)$. (Checked exhaustively at $d = 2$.)
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(N) = \Theta(3^{\,d})\) putative Non-adaptive randomness buys nothing on any function that depends on all its variables. Pick a uniformly random leaf $\ell$ and a fixed input making $\ell$ pivotal, then set $x_\ell$ uniformly at random. A non-adaptive algorithm reading $q$ positions hits $\ell$ with probability $\le q/N$, and otherwise sees a fixed string and must guess a uniform bit, so its success probability is at most $\tfrac12+\tfrac{q}{2N}$; hence $\mathrm{R}^{\mathrm{na}}_{1/3} \ge N/3$. Together with $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$ this pins the value, and no part of the open $\mathrm{R}$ exponent is needed.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(2^d\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = 2^d$. GoosPitassi14
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(2.59^{\,d}),\ O(d\,2.64944^{\,d})\) A noisy-query algorithm is randomized, so $\mathrm{N}_p \ge \mathrm{R} = \Omega(2.59^{\,d})$; amplifying each query of the optimal randomized tree by $O(\log \mathrm{R}) = O(d)$ repetitions gives $\mathrm{N}_p = O(\mathrm{R}\log \mathrm{R}) = O(d\,2.64944^{\,d})$ [FRPU94]. The whole $\mathrm{R}$ window is inherited, so the noisy exponent is open for exactly the same reason. FRPU94
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(2^{\,d}),\ O(d\,2^{\,d})\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(2^d)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. Unlike the classical side, the quantum value is pinned to within the logarithm because $\mathrm{Q} = \Theta(2^d)$ is exact [Reichardt11]. BNRdW05
\(\chi(f)\) Conflict complexity \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) $\chi = \Omega(\mathrm{bs}) = \Omega(2^d)$ [Li18], and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(1.007\cdot 2.64944^{\,d})$. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) Above $\chi = \Omega(\mathrm{bs})$ and above the recorded $\mathrm{RS} = \Omega(2^d)$; below $\mathrm{LR} \le \mathrm{R}$ [GLSS19]. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(2^d)$ and $\mathrm{LR} \le \mathrm{R}$ [BBGM22]; the generic $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ is weaker here. BBGM22
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\tfrac{1}{2} - \Theta\big((3/4)^{\,d}\big)\) putative Exactly computable, because $\mathrm{MAJ}_3$ is balanced: $\mathrm{Stab}_\rho(F\circ g^m) = \mathrm{Stab}_{\mathrm{Stab}_\rho(g)}(F)$ when $\mathbb{E}[g]=0$, and $\mathrm{MAJ}_3 = \tfrac12(x_1+x_2+x_3) - \tfrac12 x_1x_2x_3$ in $\pm 1$ gives $\Psi(\rho) := \mathrm{Stab}_\rho(\mathrm{MAJ}_3) = (3\rho+\rho^3)/4$. Since $\Psi(\rho) < \rho$ on $(0,1)$ the iterates fall to $0$, and near $0$ each step multiplies by $\Psi'(0) = 3/4$; hence $\mathrm{Stab}_\rho = \Theta((3/4)^d)$ and $\mathrm{NS}_\delta = (1-\mathrm{Stab}_{1-2\delta})/2 = \tfrac12 - \Theta((3/4)^d)$ for every constant $\delta \in (0,1/2)$. ODonnell14
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(\Theta\big((3/4)^{\,d}\big) = \Theta(N^{-0.2619})\) putative The iteration $\rho \mapsto (3\rho+\rho^3)/4$ of the \(\mathrm{NS}_{\delta}(f)\) entry, run $d$ times from any constant $\rho \in (0,1)$, converges to $0$ at rate $3/4$ per level: $\mathrm{Stab}_\rho(f) = \Theta((3/4)^d) = \Theta(N^{\log_3(3/4)}) = \Theta(N^{-0.2619})$. Recursive majority is thus noise sensitive -- a random-looking balanced function -- even though it is a read-once formula. ODonnell14
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Omega(1.732^{\,d}),\ O(2^d)\) Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = 2^d$ (sum the indicators of the $1$-certificates; all coefficients are positive, so nothing cancels), already a factor $(3/2)^d$ below $\deg = 3^d$. Lower: $\mathrm{MAJ}_3^{\circ d}$ is self-dual, so $\mathrm{ndeg}(\bar f) = \mathrm{ndeg}(f)$ and therefore $\mathrm{ndeg} = \mathrm{rdeg}$; recursive majority is a read-once $\mathsf{TC}^0$ formula, for which $\mathrm{rdeg} = \Omega(\sqrt{\deg}) = \Omega(3^{d/2}) = \Omega(1.732^{\,d})$ [IJKKKSWW23]. IJKKKSWW23
\(\mathrm{rdeg}(f)\) Rational degree \(\Omega(1.732^{\,d}),\ O(2^d)\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \mathrm{C}(f) = 2^d$ [IJKKKSWW23]. From below, read-once $\mathsf{AC}^0/\mathsf{TC}^0$ formulas satisfy $\mathrm{rdeg} = \Omega(\sqrt{\deg})$, i.e. $\Omega(3^{d/2}) = \Omega(1.732^{\,d})$ here. The remaining factor-$1.155^{\,d}$ window is an instance of the open question of whether $\mathrm{rdeg} = \deg^{\Omega(1)}$ is tight for read-once formulas. IJKKKSWW23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Omega(1.732^{\,d}),\ O(2^{d-1})\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ [deWolf03], with the \(\mathrm{ndeg}(f)\) window $[\Omega(1.732^{\,d}),\,2^d]$. Nondeterministic quantum queries are thus within a $1.155^{\,d}$ factor of the bounded-error $\mathrm{Q} = \Theta(2^d)$. deWolf03
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(2^d)\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(2^d)$. Self-duality of $\mathrm{MAJ}_3$ makes the two one-sided degrees $\widetilde{\deg}_+(f)$ and $\widetilde{\deg}_+(\bar f)$ equal, so no asymmetry can be exploited on this family.
\(\mathrm{sdeg}(f)\) Sign degree \(O(2^d)\) From $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(2^d)$. The base gate is a linear threshold function, so $\mathrm{sdeg}(\mathrm{MAJ}_3) = 1$; how fast sign degree grows under self-composition of an LTF is not known, which is why only the upper bound is recorded.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(2^d)\) At most both $\mathrm{rdeg} \le 2^d$ and $\widetilde{\deg} = \Theta(2^d)$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(2^d)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} \le 2^d$; since $\mathrm{Q} = \Theta(2^d)$ already, post-selection saves at most a constant factor unless the approximate rational degree drops below the exact one. MahadevdeWolf15

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

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

Cited as a witness by