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

EXACT-HALF

Nondeterministic degree 1 for the negation -- the engine behind the rdeg separations.

total basic arity: $n$ bits, $n$ even— also: \overline{\mathrm{EH}}_n \text{ (its negation)}

Description

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

Formal definition

$$\mathrm{EH}_n(x) = \mathbb{1}\Big[\textstyle\sum_i x_i = \tfrac n2\Big], \qquad \overline{\mathrm{EH}}_n(x) = 1 - \mathrm{EH}_n(x).$$ The point: $q(x)=\sum_i x_i - n/2$ vanishes exactly on $\overline{\mathrm{EH}}_n^{-1}(0)$, so $\mathrm{ndeg}(\overline{\mathrm{EH}}_n)=1$ -- the smallest possible for a non-constant function.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(n\)
\(\deg(f)\) Exact degree \(n\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(n)\) Paturi92
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(n)\)
\(\mathrm{s}^1(f)\) 1-sensitivity \(n\)
\(\mathrm{s}^0(f)\) 0-sensitivity \(n/2 + 1\)
\(\mathrm{s}(f)\) Sensitivity \(n\)
\(\lambda(f)\) Spectral sensitivity \(\sqrt{n(n/2+1)}\) putative Exactly, and for $\mathrm{EH}_n$ itself (spectral sensitivity is insensitive to negation, since $f$ and $\bar f$ have the same sensitivity graph, so the same number is also $\lambda(\overline{\mathrm{EH}}_n)$). The sensitivity graph has an edge $(x,x^{\oplus i})$ exactly when one endpoint has weight $n/2$, so it is bipartite between the middle layer and the two layers $n/2\pm1$. It is biregular: a middle vertex has degree $n$, and a vertex of weight $n/2-1$ or $n/2+1$ has degree $n/2+1$. The vector giving $\sqrt n$ to each vertex of the second side and $\sqrt{n/2+1}$ to each middle vertex is positive with eigenvalue $\sqrt{n(n/2+1)}$, so by Perron--Frobenius that is the spectral radius. This meets the general bound $\lambda(f)\le\sqrt{\mathrm{s}^0(f)\,\mathrm{s}^1(f)}$ with equality, since $\mathrm{s}^1 = n$ and $\mathrm{s}^0 = n/2+1$ -- so $\mathrm{EH}$ is an exact witness for that inequality, and $\lambda = n/\sqrt2\,(1+o(1))$ sits strictly between the two. ABKRT21
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(n/2\) putative Exactly $n/2$, for $\mathrm{EH}_n$ itself. Upper bound: for a perfect matching $M$ of $[n]$ put $q_M(x)=\prod_{(i,j)\in M}(x_i-x_j)$, of degree $n/2$; it is nonzero iff every pair of $M$ is split, which forces $|x| = n/2$, and every middle input is split by some matching. So a generic combination $\sum_M a_M q_M$ is nonzero exactly on the middle slice. Lower bound: if $p$ is nonzero exactly on $\mathrm{EH}^{-1}(1)$ then $p^2$ is nonnegative with the same zero set, so its symmetrisation $P(k)=\mathbb{E}_{|x|=k}[p(x)^2]$ is a univariate polynomial of degree $\le 2\deg p$ vanishing at all $n$ points $k \ne n/2$ of $\{0,\dots,n\}$; hence $\deg p \ge n/2$. Contrast $\mathrm{ndeg}(\overline{\mathrm{EH}}_n) = 1$, witnessed by $\sum_i x_i - n/2$: this factor-$n/2$ asymmetry between a function and its negation is what \(\mathrm{EH}_n\) is for, and it is what makes $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} = n/2$ here. IJKKKSWW23
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\)
\(\mathrm{bs}(f)\) Block sensitivity \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{bs}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{C}(f)\) Certificate complexity \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{bs}^1(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\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{R}_{0}(f)\) Zero-error randomized query complexity \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\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)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\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{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) $\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) = 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{Adv}(f)\) Positive-weights adversary bound \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with both ends $\Theta(n)$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}^1(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}^1(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\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 = (n/2+1)\cdot n = \Theta(n^2)$ [CGLMSG23]. Above the arity, for the same reason as \(\mathrm{MAJ}_n\): the sensitivity graph is biregular of degree $\Theta(n)$ on the middle slice, so $\lambda = \Theta(n)$. CGLMSG23
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\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.
\(\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.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(n\) putative A $1$-input has weight exactly $n/2$, and flipping any single unfixed coordinate leaves the middle slice, so a $1$-certificate must fix all $n$ coordinates. This is the value that makes $\mathrm{C} = n$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n/2 + 1\) putative A partial assignment with $a$ ones and $b$ zeros forces the answer $0$ exactly when $a > n/2$ or $b > n/2$, so the cheapest $0$-certificate exhibits $n/2+1$ equal bits, and every $0$-input has one. Matches $\mathrm{s}^0 = n/2+1$, so blocks and fractional relaxations buy nothing on the $0$-side.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(n/2 + 1\) Sandwiched: $\mathrm{s}^0(f) \le \mathrm{bs}^0(f) \le \mathrm{C}^0(f)$, with both ends $n/2+1$ here.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(n/2 + 1\) putative Every $0$-input costs $n/2+1$ and every $1$-input costs $n$, so the minimum is the $0$-side value. The factor-$2$ gap to $\mathrm{C} = n$ is the whole of the asymmetry of $\mathrm{EH}$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(n\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $n$ here. GJKKLSSV17
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{SP}(f)\) Subcube partition complexity \(n\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with both ends $n$ here. The $1$-inputs are isolated points of the cube, so no monochromatic subcube containing one can have codimension below $n$.
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(n)\) $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$, and symmetric functions have $\mathrm{rdeg} = \Omega(\deg)$ (see \(f = f(|x|)\)). Since $\mathrm{ndeg}(\overline{\mathrm{EH}}) = 1$, the whole of $\mathrm{rdeg}$ comes from $\mathrm{ndeg}(\mathrm{EH}) = \Theta(n)$ -- this is precisely the $\mathrm{ndeg}$-versus-$\mathrm{rdeg}$ separation that $\mathrm{EH}$ is famous for. IJKKKSWW23
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BenDavidKothari18
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. So verifying is quadratically cheaper even though computing costs the full $\Theta(n)$ quantumly. Aaronson08
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(\sqrt n)\) putative Coordinate $i$ is pivotal exactly when the other $n-1$ bits have weight $n/2$ or $n/2-1$, so $\mathrm{Inf}_i = \binom{n}{n/2}2^{1-n} = \Theta(1/\sqrt n)$ and the total is $\Theta(\sqrt n)$ -- the same order as \(\mathrm{MAJ}_n\), despite $\mathrm{EH}$ being exponentially unbalanced.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(\sqrt n)\) Boolean-valued, so equal to $\mathrm{I}(f)$.
\(\mathrm{MaxInf}(f)\) Maximum influence \(\binom{n}{n/2}2^{1-n}\) putative The family is transitive, so every coordinate carries $\mathrm{I}(f)/n = \Theta(1/\sqrt n)$.
\(\mathrm{Var}(f)\) Variance \(4M(1-M) = \Theta(1/\sqrt n),\quad M = \binom{n}{n/2}2^{-n}\) The Fourier weight above level $0$, as noted in the \(\mathrm{Stab}_{\rho}(f)\) entry.
\(\mathrm{osss}(f)\) OSSS number \(2(1-M) = 2-\Theta(1/\sqrt n)\) putative $\mathrm{MaxInf} = 2M$ exactly, so the ratio is $4M(1-M)/(2M) = 2(1-M)$. Normalizing rescues nothing here: both numerator and denominator are $\Theta(1/\sqrt n)$, and the bound certifies two queries against $\mathrm{D} = n$.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(n)\) putative At $\delta = c/n$ the number of flipped bits is $\mathrm{Poisson}(c)$-like, and a $1$-input survives only if the flips are exactly balanced between the two halves, which fails with probability bounded away from $0$ and $1$. So $\delta^{*} = \Theta(1/n)$ and the value is tight against $\mathrm{nsr} = O(\mathrm{s}) = O(n)$ and against $\mathrm{D} = n$.
\(\mathrm{rank}(f)\) Decision tree rank \(n/2 + 1\) putative Prover-Delayer: the value stays undetermined until one of the two counts reaches $n/2+1$, and until then the Delayer may defer on every query, so she scores $n/2+1$; the counting tree, which stops as soon as either count passes $n/2$, attains it. Same value as \(\mathrm{MAJ}_n\) -- exactness costs nothing in rank, only in depth on the $1$-side.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) putative Fix $n/2$ coordinates to be $1$ with probability $1$ and give each of the other $n/2$ probability $2/n$. Then $\mathrm{EH} = 1$ exactly when none of the low-probability bits fires, which happens with probability $\to e^{-1} > 1/3$, and deciding that is $\mathrm{OR}$ under its own hard product distribution: after $m$ zeros the conditional probability of a remaining $1$ is still $1 - (1-2/n)^{n/2-m}$. So $m = \Omega(n)$, and product distributions are already worst case.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(n)\) Sandwiched between $\mathrm{Q} = \Theta(n)$ and the universal $O(n)$ robust upper bound. BNRdW05
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(n\log n)\)· putative Upper: $O(\mathrm{R}\log \mathrm{R})$ by repeating each query. Lower: as for \(\mathrm{MAJ}_n\), only more so -- the answer changes when a single bit moves the weight off $n/2$, so every coordinate must be resolved to error $o(1/n)$, costing $\Omega(\log n)$ repetitions each. FRPU94
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(n-1\) putative $\mathrm{EH}_n(\bar x) = \mathrm{EH}_n(x)$, so only even-size sets carry Fourier weight and the support lies in the even-weight subspace of $\mathbb{F}_2^n$, of dimension $n-1$. It spans that subspace: every level-$2$ coefficient is nonzero, since conditioned on the middle slice $\mathbb{E}[X_iX_j] = -1/(n-1) \ne 0$. Note the singletons all vanish -- $\mathrm{EH}$ has no linear part at all.
\(\deg_2(f)\) Mod-2 degree \(n-1\) putative Recorded along the subfamily $n = 2^m$. The $\mathbb{F}_2$ coefficient of the monomial $\prod_{i\in S}x_i$ in $\mathrm{EH}_n$ is $\binom{|S|}{n/2} \bmod 2$, so $\deg_2$ is the largest $s \le n$ whose binary expansion contains that of $n/2$ (Lucas). For $n = 2^m$ the bit $2^{m-1}$ is absent from $n$ itself, and the largest admissible $s$ is $n-1 = 2^m-1$. For other $n$ the answer jumps around -- e.g. $\deg_2(\mathrm{EH}_6) = 3$ -- which is why the value is recorded on a subfamily.
\(\mathrm{sdeg}(f)\) Sign degree \(2\) A symmetric function has threshold degree equal to the number of sign changes of its slice pattern, and $\mathrm{EH}$ changes sign twice. Explicitly $p(x) = \tfrac14 - \big(\sum_i x_i - \tfrac n2\big)^2$ is positive exactly on the middle slice. So $\mathrm{sdeg} = 2$ against $\widetilde{\deg} = \Theta(n)$. Threshold degree is not a lower bound on anything interesting on its own: \(\mathrm{MAJ}_n\) does even better with $\mathrm{sdeg} = 1$, and the point of \(\mathrm{MP}_m\) is that a small-depth function can force $\mathrm{sdeg}$ up at all. What makes $\mathrm{EH}$ instructive is that its two sign changes are forced -- one is not enough for a non-monotone slice pattern -- so the exact value is $2$ rather than merely $O(1)$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\lceil n/4 \rceil\) $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ [deWolf00] applied to the $\mathrm{ndeg} = n/2$ line above. For the negation the same formula gives $\mathrm{NQ}(\overline{\mathrm{EH}}_n) = 1$: one nondeterministic query certifies inequality to $n/2$, while $n/4$ are needed to certify equality. deWolf00
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) putative Lower: $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17] with $\mathrm{fbs} = n$ gives $\mathrm{UC}_{\min} \ge (n+1)/2$. Upper: $\mathrm{UC}_{\min} \le \mathrm{UC}^1 = n$, the $1$-inputs being isolated points, which the partition into singletons covers unambiguously. The exact constant is open here; note that no unambiguous $0$-cover can use only minimum $0$-certificates, since two all-ones certificates of size $n/2+1$ must overlap in a coordinate and their subcubes then share the input $1_{S \cup T}$. BHT17
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(n)\) putative Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. Lower by granularity: in the $\pm1$ encoding the top coefficient is $\hat g([n]) = \mp\binom{n}{n/2}2^{1-n}$, and $\nu_2\binom{n}{n/2}$ equals the number of carries in adding $n/2 + n/2$ in base $2$, namely the binary digit sum of $n/2$ (Kummer). So the granularity is at least $n-1-\log_2 n$ and $\mathrm{D}^{\oplus} \ge n - \log_2 n$. Along $n = 2^m$ the digit sum is $1$, pinning $\mathrm{D}^{\oplus}$ to $n-1$ or $n$: parity queries buy at most one query on the middle slice. ChistopolskayaPodolskii18
\(\mathrm{DTsize}(f)\) Decision tree size \(\Theta(2^n/\sqrt n)\) putative Lower: $\mathrm{C}^1 = n$, so every $1$-leaf is a single point of the cube and the tree needs $\binom{n}{n/2}$ of them. Upper: the counting tree -- read $x_1,x_2,\dots$ and halt as soon as either count exceeds $n/2$ -- has $\binom{n}{n/2} + 2\binom{n}{n/2+1}$ leaves. Both ends are $\Theta(2^n/\sqrt n)$.
\(\mathrm{spar}(f)\) Fourier sparsity \(2^{n-1}\) putative Exactly. Using $\binom ns K_k(s) = \binom nk K_s(k)$ and $K_s(n/2) = [z^s](1-z)^{n/2}(1+z)^{n/2} = [z^s](1-z^2)^{n/2}$, the Fourier coefficient at a set of size $s$ is $\widehat{\mathrm{EH}}(S) = 2^{-n}\binom{n}{n/2}(-1)^{s/2}\binom{n/2}{s/2}\big/\binom ns$ for even $s$, and $0$ for odd $s$. So every even-size set carries a nonzero coefficient and no odd one does -- consistent with the recorded $\mathrm{Fdim} = n-1$.
\(\hat{L}_1(f)\) Spectral norm \(\Theta(2^{n/2}/\sqrt n)\) putative Exactly $\binom{n}{n/2}2^{-n/2}$, from the closed form on the \(\mathrm{spar}(f)\) line: the binomials $\binom ns$ cancel and $\hat L_1 = 2^{-n}\binom{n}{n/2}\sum_{t}\binom{n/2}{t} = 2^{-n/2}\binom{n}{n/2}$. Asymptotically $\sqrt{2/\pi}\,2^{n/2}n^{-1/2}$ -- the same order as \(\mathrm{MAJ}_n\), and within $\sqrt n$ of the maximum possible, which is what Cauchy--Schwarz against $\mathrm{spar} = 2^{n-1}$ predicts.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\Theta(1/\sqrt n)\) putative For every fixed $\delta \in (0,1/2)$. $\mathrm{NS}_\delta = 2\big(M - \Pr[\mathrm{EH}(x)=\mathrm{EH}(y)=1]\big)$ with $M = \binom{n}{n/2}2^{-n} = \Theta(n^{-1/2})$, and the joint probability is $M^2\sum_t \rho^{2t}\binom{n/2}{t}^2/\binom{n}{2t} \to M^2/\sqrt{1-\rho^2}$ at $\rho = 1-2\delta$, of order $1/n$. So $\mathrm{NS}_\delta = 2M(1-o(1))$: noise almost always destroys a $1$, but $1$s are rare, so the function is noise stable in the crude sense while carrying no low-degree structure at all.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - \Theta(1/\sqrt n)\) putative The \(\mathrm{NS}_{\delta}(f)\) line through $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$, for every fixed $\rho \in (-1,1)$. The exponentially unbalanced $\pm1$ encoding is what makes this tend to $1$; the whole spectrum above level $0$ carries weight only $4M(1-M) = \Theta(n^{-1/2})$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(n)\) putative Equal to $\widetilde{\deg}$, by a normalisation that works because the $1$-inputs form a single slice. Symmetrising a one-sided approximant $p$ gives a univariate $P$ of degree $\le \deg p$ with $|P(k)| \le 1/3$ for $k \ne n/2$ and $M := P(n/2) \ge 2/3$; the one-sided model puts no ceiling on $M$. Now replace $P$ by $P/\max\{1,M\}$. If $M \le 1$ nothing changes and the error at $n/2$ is $1-M \le 1/3$; if $M > 1$ the error at $n/2$ becomes $0$ and the errors elsewhere only shrink. Either way the result is a genuine two-sided $1/3$-approximation, so $\mathrm{odeg} \ge \widetilde{\deg} = \Theta(n)$ [Paturi92]. One-sidedness saves nothing here, in sharp contrast with \(\mathrm{OR}_n\), where $3\sum_i x_i$ gives $\mathrm{odeg} = 1$ against $\widetilde{\deg} = \Theta(\sqrt n)$ -- the difference being that $\mathrm{OR}$ has $1$-inputs on every slice, so no single rescaling can tame them. Paturi92
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(1)\) putative Degree $2$ suffices: $r(x) = \big(1 + 2(\sum_i x_i - n/2)^2\big)^{-1}$ equals $1$ on the middle slice and is at most $1/3$ everywhere else, since $|\sum_i x_i - n/2| \ge 1$ off it. This is the sharpest gap in the zoo between rational and polynomial approximation: $\widetilde{\deg} = \Theta(n)$ and even $\mathrm{rdeg} = \Theta(n)$ (exact rational representation), yet approximate rational degree is constant. Recorded as $O(1)$ because $\ge 2$ is not proved -- only $\ge 1$ from non-constancy. MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(1)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15] applied to the \(\mathrm{rdeg}_{\varepsilon}(f)\) line: a postselecting quantum algorithm decides $\mathrm{EH}_n$ with $O(1)$ queries while $\mathrm{Q} = \Theta(n)$, the largest possible separation. MahadevdeWolf15
\(\deg_p(f)\) Mod-p degree \(\Theta(n)\) putative For every prime $p$. The coefficient of $\prod_{i \in S}x_i$ in the integer multilinear expansion is $(-1)^{|S|-n/2}\binom{|S|}{n/2}$, so $\deg_p$ is the largest $s \le n$ with $\binom{s}{n/2} \not\equiv 0 \pmod p$. Taking $s = n/2$ gives $\binom{n/2}{n/2} = 1$, so $\deg_p \ge n/2$ in every characteristic, and $\deg_p \le n$ trivially. Which $s$ is largest jumps around with $p$ and $n$ by Lucas -- see the \(\deg_2(f)\) line for the $p=2$ story -- but the order is always $n$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform distribution already attains it. Yao77
\(\mathrm{cbs}(S)\) Critical block sensitivity \(n\) 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$ here, attained at any input of weight $n/2$. 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

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

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