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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = n/2 + 1\) against \(\mathrm{PostQ}_{\varepsilon}(f) = O(1)\)
-
\(\mathrm{D}^{\mathrm{prod}}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{prod}}(f) = \Theta(n)\) against \(\mathrm{Stab}_{\rho}(f) = 1 - \Theta(1/\sqrt n)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{rank}(f) = n/2 + 1\) against \(\mathrm{rdeg}_{\varepsilon}(f) = O(1)\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{osss}(f_n) = O(1)\)from \(\hat{L}_1(f) = \Theta(2^{n/2}/\sqrt n)\) against \(\mathrm{osss}(f) = 2(1-M) = 2-\Theta(1/\sqrt n)\)
-
\(\mathrm{CG}(f_n) = \Omega\big(\deg_p(f_n)^{2}\big)\)from \(\mathrm{CG}(f) = \Theta(n^2)\) against \(\deg_p(f) = \Theta(n)\)
-
\(\mathrm{nsr}(f_n) = \Omega\big(\mathrm{I}(f_n)^{2}\big)\)from \(\mathrm{nsr}(f) = \Theta(n)\) against \(\mathrm{I}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = n/2 + 1\) against \(\mathrm{rdeg}_{\varepsilon}(f) = O(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{rank}(f) = n/2 + 1\) against \(\mathrm{PostQ}_{\varepsilon}(f) = O(1)\)
-
\(\mathrm{rdeg}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{rdeg}(f) = \Theta(n)\) against \(\mathrm{Stab}_{\rho}(f) = 1 - \Theta(1/\sqrt n)\)
-
\(\hat{L}_1(f_n) = 2^{\Omega(\mathrm{D}^{\oplus}(f_n))}\)from \(\hat{L}_1(f) = \Theta(2^{n/2}/\sqrt n)\) against \(\mathrm{D}^{\oplus}(f) = \Theta(n)\)
-
\(\mathrm{nsr}(f_n) = \Omega\big(\mathrm{I}^{1}(f_n)^{2}\big)\)from \(\mathrm{nsr}(f) = \Theta(n)\) against \(\mathrm{I}^{1}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{Adv}(f_n) = \Omega\big(\deg_p(f_n)\big)\)from \(\mathrm{Adv}(f) = \Theta(n)\) against \(\deg_p(f) = \Theta(n)\)
-
\(\mathrm{ndeg}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{ndeg}(f) = n/2\) against \(\mathrm{Stab}_{\rho}(f) = 1 - \Theta(1/\sqrt n)\)
-
\(\mathrm{cjdeg}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{cjdeg}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{PostQ}_{\varepsilon}(f) = O(1)\)
… and 16 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.