\(\oplus_n\)
PARITY
Maximally hard for every measure in the zoo except parity decision trees -- hence the witness for every "$1,1$" cell.
total
basic
arity: $n$ bits— also: XOR, MOD_2
Description
$\oplus_n(x) = x_1 \oplus \cdots \oplus x_n$.
Formal definition
$$\oplus_n(x) = \sum_{i=1}^n x_i \bmod 2,\qquad\text{Fourier: } (-1)^{\oplus_n(x)} = \prod_{i=1}^n (-1)^{x_i}=\chi_{[n]}(x).$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n\) | |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(n\) | |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(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 | \(\lceil n/2 \rceil\) | One query decides the parity of two bits (Deutsch); this is exactly tight. BBCMdW01 |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\lceil n/2 \rceil\) | BBCMdW01 |
| \(\deg(f)\) Exact degree | \(n\) | |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(n\) | |
| \(\mathrm{sdeg}(f)\) Sign degree | \(n\) | MinskyPapert69 |
| \(\mathrm{s}(f)\) Sensitivity | \(n\) | |
| \(\mathrm{bs}(f)\) Block sensitivity | \(n\) | |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(n\) | |
| \(\mathrm{C}(f)\) Certificate complexity | \(n\) | |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\lceil n/2\rceil\) putative | A verifier must catch the flip of any single bit with probability $\ge 1/2$, so $\Pr[i \in S]\ge 1/2$ for every $i$ and $\mathbb{E}|S| \ge n/2$; a uniformly random half attains it. Note $\mathrm{RC} \ne \mathrm{fbs} = n$ here -- the constant in $\mathrm{RC}=\Theta(\mathrm{fbs})$ is real. |
| \(\lambda(f)\) Spectral sensitivity | \(n\) | Sensitivity graph is the whole hypercube, which is $n$-regular. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(n\) | |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(n\) | |
| \(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity | \(1\) | One parity query. The reason $\mathrm{D}^{\oplus}$ is a genuinely different measure. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(n\) | |
| \(\mathrm{spar}(f)\) Fourier sparsity | \(1\) | |
| \(\hat{L}_1(f)\) Spectral norm | \(1\) | |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Theta(n\log n)\) | The canonical example where constant-rate noise costs a $\log n$ factor; matching upper bound in [FRPU94], matching lower bound in [EvansPippenger98]. FRPU94 EvansPippenger98 |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(n\) | |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(n\) | |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(n\) | |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(n\) | |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(n\) | |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(n\) | |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(n\) | Every input needs the whole assignment; PARITY is evasive in the strongest sense. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(n\) | |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(n\) | Between $\mathrm{fbs}=n$ and $\mathrm{C}=n$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(n\) | The full binary tree is already an unambiguous partition, and $\mathrm{UC}\ge\mathrm{C}=n$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(n\) | Every certificate of every input is the whole assignment. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(n\) | A monochromatic subcube must fix every coordinate. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(n\) | Both children of every node of every tree for $\oplus_n$ compute a parity of the remaining variables, so the two ranks are equal at every level and the rank climbs by one each time. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^n\) | Every leaf is a full assignment. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n\) | |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(n\) | Leaving any coordinate unqueried leaves the answer a fair coin flip. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\lceil n/2 \rceil\) | Sandwiched between $\mathrm{Q}=\lceil n/2\rceil$ and $\mathrm{Q_E}=\lceil n/2\rceil$. BBCMdW01 |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\lceil n/2 \rceil\) | $\mathrm{ndeg}(\oplus_n)=n$. deWolf03 |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(\sqrt n)\) | $\mathrm{QC}=\Theta(\sqrt{\mathrm{RC}})$ and $\mathrm{RC}=\lceil n/2\rceil$. Verification is quadratically cheaper than computation even here. Aaronson08 |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(n\) | Squeezed between $\mathrm{sdeg}=n$ and $\widetilde{\deg}=n$. |
| \(\deg_2(f)\) Mod-2 degree | \(1\) | Over $\mathbb{F}_2$ parity is linear -- the reason $\mathrm{D}^{\oplus}=1$. |
| \(\dim_{\mathbb{F}_2}(f)\) Fourier dimension | \(1\) | The Fourier support is the single set $[n]$. |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(1\) | Every coordinate is always sensitive. |
| \(\mathrm{Var}(f)\) Variance | \(1\) | Perfectly balanced, so $\mathrm{Var} = 4\cdot\tfrac12\cdot\tfrac12 = 1$ -- the maximum. |
| \(\mathrm{osss}(f)\) OSSS number | \(1\) putative | The smallest value the measure can take: $\mathrm{MaxInf} = \mathrm{Var} = 1$, because a single coordinate is pivotal on every input. OSSS therefore certifies one query against $\mathrm{D} = n$, the extreme demonstration that the bound is only as good as the spread of the influences. |
| \(\mathrm{nsr}(f)\) Noise robustness | \(2n/\ln 2\,(1+o(1)) = \Theta(n)\) putative | $\tfrac12(1-(1-2\delta)^n) = \tfrac14$ at $(1-2\delta)^n = \tfrac12$, so $\delta^{*} = (\ln 2)/(2n)(1+o(1))$. Maximally noise-robust at the scale that matters, which is the opposite reading of the same function from $\mathrm{NS}_{1/2} = \tfrac12$. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(n\) | Boolean-valued, so the $L_1$ and $L_2$ influences agree. |
| \(\mathrm{NS}_{\delta}(f)\) Noise sensitivity | \(\tfrac12\big(1-(1-2\delta)^n\big)\) | Exactly: the noise flips the answer iff an odd number of bits flip. Maximally noise-sensitive. ODonnell14 |
| \(\mathrm{Stab}_{\rho}(f)\) Noise stability | \(\rho^{\,n}\) | ODonnell14 |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(n)\) | At most $\mathrm{R}=n$; and a sabotaged input with a single $\ast$ hides it among $n$ positions. BenDavidKothari18 |
| \(\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}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(\lceil n/2 \rceil)\) | $\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) = \lceil n/2 \rceil$ here. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(\lceil n/2 \rceil)\) | $\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) = \lceil n/2 \rceil$ here. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(n/2\) | $\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} = n/2$. Spalek08 |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(n\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\chi(f)\) Conflict complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(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 both ends $n$ here. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Theta(n^2)\) | The headline case for this measure: above the arity. From below $\mathrm{CG} \ge \mathrm{Adv}^2 = n^2$ -- equivalently the Hamming-distance-$1$ game already costs $\lambda^2 = n^2$, since two players who differ in one unknown coordinate must each guess it out of $n$ independently. From above $\mathrm{C}^0\mathrm{C}^1 = n^2$. Both [CGLMSG23] bounds are tight on parity, and the result is quadratically larger than $\mathrm{D} = n$: private-coin certificate games are the one variant of the four that is not capped by decision-tree complexity. CGLMSG23 |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(n)\) | Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(n\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $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 both ends $n$ here. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(n\) | Rational approximation does not help at all here. Suppose $p/q$ approximates $\mathrm{PARITY}$ to within $1/3$ with $\deg p, \deg q \le d$ and $q > 0$ on the cube. Symmetrising over the slices, $P(k) - \tfrac12 Q(k)$ is a univariate polynomial of degree $\le d$ whose sign alternates at $k = 0,1,\dots,n$, so it has $\ge n$ roots and $d \ge n$. Contrast $\mathrm{rdeg}(\mathrm{MAJ}) = \Theta(\log n)$: parity is the function on which postselection buys nothing. MahadevdeWolf15 |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(n)\) | From $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(n)$. Even $\mathsf{PostBQP}$ needs to read essentially the whole input. MahadevdeWolf15 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Theta(n)\) | The headline robustness result: $n$ noisy quantum queries recover all $n$ bits, so $\mathrm{Q}^{\mathrm{rob}} = O(n)$, matching $\mathrm{Q} = n/2$ up to a constant. Classically the same task costs $\Theta(n\log n)$ [FRPU94] -- noise imposes a logarithmic tax on randomized algorithms that quantum algorithms simply do not pay. An explicit degree-$O(n)$ robust polynomial was later given by [Sherstov13robust]. BNRdW05 FRPU94 |
| \(\deg_p(f)\) Mod-p degree | \(1 \text{ if } p = 2;\ n \text{ if } p > 2\) | Over $\mathbb{F}_2$ parity is the linear form $\sum_i x_i$. For odd $p$ the multilinear representation is $\tfrac12\big(1 - \prod_i(1-2x_i)\big)$, whose top coefficient $\pm 2^{n-1}$ is a unit mod $p$, so the degree jumps back to $n$. This single function is the whole content of the $\deg_p$ column. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(n\) | Under the uniform $\mu$, for every $\varepsilon < 1/2$ -- and since $\mathrm{D}^\mu \le \mathrm{D} = n$ for every $\mu$, the uniform distribution is simultaneously the hardest one, so no choice of $\mu$ has to be recorded alongside the value. Every leaf of a tree of depth $< n$ leaves some coordinate unqueried, and conditioned on the queried bits the parity is still uniform on $\{0,1\}$; so any such tree errs with probability exactly $1/2$ under the uniform distribution. This is the extreme point of Yao's principle: one distribution already witnesses the worst case, with no slack. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(n\) | The uniform distribution is a product distribution, and $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = n$. |
| \(\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 both ends $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{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)$: every one of the $n$ coordinates is sensitive at every input. GoosPitassi14 |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(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))$, and $\mathrm{R} = \mathrm{D} = n$ here, so all three of $\mathrm{R}$, $\mathrm{psD}$ and $\mathrm{D}$ coincide exactly. CDM23 |
| \(\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\) | Theorem 42: λcert=√s, with s=n. 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. 1517 in total, strongest first.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\oplus}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{D}^{\oplus}(f) = 1\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \deg_2(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = 2^n\) against \(\deg_2(f) = 1\)
-
\(\mathrm{s}(f_n) \to \infty \ \text{ while } \ \mathrm{Var}(f_n) = O(1)\)from \(\mathrm{s}(f) = n\) against \(\mathrm{Var}(f) = 1\)
-
\(\mathrm{s}^0(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\mathrm{s}^0(f) = n\) against \(\mathrm{MaxInf}(f) = 1\)
-
\(\mathrm{s}^1(f_n) \to \infty \ \text{ while } \ \mathrm{spar}(f_n) = O(1)\)from \(\mathrm{s}^1(f) = n\) against \(\mathrm{spar}(f) = 1\)
-
\(\mathrm{bs}(f_n) \to \infty \ \text{ while } \ \dim_{\mathbb{F}_2}(f_n) = O(1)\)from \(\mathrm{bs}(f) = n\) against \(\dim_{\mathbb{F}_2}(f) = 1\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{osss}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = n\) against \(\mathrm{osss}(f) = 1\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \hat{L}_1(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = n\) against \(\hat{L}_1(f) = 1\)
-
\(\mathrm{CG}(f_n) = \Omega\big(\mathrm{QC}(f_n)^{4}\big)\)from \(\mathrm{CG}(f) = \Theta(n^2)\) against \(\mathrm{QC}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{rank}(f_n) = \Omega\big(\mathrm{QS}_{\mathrm{weak}}(f_n)^{2}\big)\)from \(\mathrm{rank}(f) = n\) against \(\mathrm{QS}_{\mathrm{weak}}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{N}_{p}(f_n) = \Omega\big(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f_n)^{2}\big)\)from \(\mathrm{N}_{p}(f) = \Theta(n\log n)\) against \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{PostQ}_{\varepsilon}(f_n) = \Omega\big(\mathrm{QS}_{\mathrm{str}}(f_n)^{2}\big)\)from \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{QS}_{\mathrm{str}}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{Q}^{\mathrm{rob}}(f_n) = \Omega\big(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f_n)^{2}\big)\)from \(\mathrm{Q}^{\mathrm{rob}}(f) = \Theta(n)\) against \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f) = \Theta(\sqrt n)\)
-
\(\lambda(f_n) = \Omega\big(\lambda^{\mathrm{cert}}(f_n)^{2}\big)\)from \(\lambda(f) = n\) against \(\lambda^{\mathrm{cert}}(f) = \sqrt n\)
… and 1503 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
general totalEvery classical measure equals $n$, so PARITY certifies that all the "$1,1$" cells of the matrix are tight -- no measure in the left column can be asymptotically smaller than any in the top row on this family.
-
$\mathrm{D}=n$ but $\mathrm{D}^{\oplus}=1$: parity decision trees are incomparable to ordinary ones.
-
$\mathrm{N}_p = \Theta(n\log n)$ vs $\mathrm{D}=n$: noise genuinely costs a logarithm.
Cited as a witness by
-
\(\mathrm{bs}(f_n) = \Omega(\mathrm{R}(f_n))\)
-
\(\mathrm{RC}(f_n) = \Omega(\mathrm{C}(f_n))\)
-
\(\mathrm{s}(f_n) = \mathrm{D}(f_n) = n\)
-
\(\mathrm{C}(\oplus_n) = \mathrm{SP}(\oplus_n) = n\)
-
\(\mathrm{UC}(\oplus_n) = \mathrm{SP}(\oplus_n) = n\)
-
\(\mathrm{SP}(\oplus_n) = \mathrm{UC}(\oplus_n) = n\)
-
\(\widetilde{\deg}(\mathrm{PARITY}_n) = \mathrm{R}(\mathrm{PARITY}_n) = n\)
-
\(\deg_{\pm}(\oplus_n) = n = 2\,\mathrm{rdeg}(\oplus_n)\)
-
\(\deg(\mathrm{PARITY}_n) = n = 2\,\mathrm{Q}_E(\mathrm{PARITY}_n)\)
-
\(\widetilde{\deg}(\mathrm{PARITY}_n) = n = 2\,\mathrm{Q}(\mathrm{PARITY}_n)\)
-
\(\mathrm{Q}(\mathrm{PARITY}_n) = \lceil n/2\rceil\)
-
\(\lambda(\mathrm{PARITY}_n) = n,\ \mathrm{Q}(\mathrm{PARITY}_n)=\lceil n/2\rceil\)
-
\(\lambda(\mathrm{PARITY}_n) = \mathrm{s}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{Adv}(\oplus_n) = \mathrm{C}(\oplus_n) = n\)
-
\(\mathrm{Adv}(\oplus_n) = \widetilde{\deg}(\oplus_n) = n\)
-
\(\mathrm{Q}^{\mathrm{rob}}(\mathrm{PARITY}_n) = \Theta(n)\)
-
\(\mathrm{I}(\mathrm{PARITY}_n) = n,\quad \mathrm{N}_p(\mathrm{PARITY}_n) = \Theta(n\log n)\)
-
\(\mathrm{N}_p(\mathrm{PARITY}_n) = \Theta(n\log n)\)
-
\(\mathrm{I}(f) \le \mathrm{s}(f)\)
-
\(\mathrm{I}(\mathrm{PARITY}_n) = \mathrm{s}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{I}(\mathrm{PARITY}_n)=\deg(\mathrm{PARITY}_n)=n\)
-
\(\mathrm{I}(\mathrm{PARITY}_n)=n,\ \widetilde{\deg}(\mathrm{PARITY}_n)=n\)
-
\(\mathrm{I}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\deg(\oplus_n) = n,\quad \mathrm{spar}(\oplus_n) = 1\)
-
\(\deg_p(\oplus_n) = n \ \text{ for every odd prime } p, \quad \mathrm{spar}(\oplus_n) = 1\)
-
\(\mathrm{osss}(\oplus_n) = 1 = \mathrm{spar}(\oplus_n)\)
-
\(\mathrm{cbs}(\oplus_n) = \mathrm{bs}(\oplus_n) = n, \quad \mathrm{D}^{\oplus}(\oplus_n) = 1\)
-
\(\mathrm{psD}(\oplus_n) = \Theta(\mathrm{R}(\oplus_n)) = \Theta(n), \quad \mathrm{D}^{\oplus}(\oplus_n) = 1\)
-
\(\mathrm{N}_p(\oplus_n) = \Theta(n\log n) = \Theta(\mathrm{cbs}\,\log \mathrm{cbs})\)
-
\(\mathrm{Adv}(\oplus_n) = \Theta(n) = \Theta(\mathrm{cbs}(\oplus_n))\)
-
\(\mathrm{N}_p(\oplus_n) = \Theta(n\log n) = \Theta(\mathrm{psD}\,\log \mathrm{psD})\)
-
\(\mathrm{Adv}(\oplus_n) = \Theta(n) = \Theta(\mathrm{psD}(\oplus_n))\)
-
\(\mathrm{cjdeg}(\oplus_n) = n = \Theta(\mathrm{psD}(\oplus_n))\)
-
\(\mathrm{R}_0(\mathrm{PARITY}_n) = \mathrm{D}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{C}(\mathrm{PARITY}_n) = \mathrm{D}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{C}(\mathrm{PARITY}_n) = \mathrm{R}_0(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{R}(\mathrm{PARITY}_n) = \mathrm{R}_0(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{R}(\mathrm{PARITY}_n) = \mathrm{D}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{Q}(\mathrm{PARITY}_n) = \lceil n/2\rceil = \tfrac12\,\mathrm{R}(\mathrm{PARITY}_n)\)
-
\(\mathrm{Q}(\mathrm{PARITY}_n) = \mathrm{Q}_0(\mathrm{PARITY}_n) = \lceil n/2\rceil\)
-
\(\deg(\mathrm{PARITY}_n) = \mathrm{D}(\mathrm{PARITY}_n) = n\)
-
\(\widetilde{\deg}(\mathrm{PARITY}_n) = \deg(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{rdeg}(\mathrm{PARITY}_n) = \mathrm{C}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{rank}(\mathrm{PARITY}_n) = \mathrm{D}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{rank}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{C}_{\min}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{D}(\mathrm{PARITY}_n) = \mathrm{D}^{\mathrm{na}}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{R}(\mathrm{PARITY}_n) = \mathrm{R}^{\mathrm{na}}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{R}^{\mathrm{na}}(\mathrm{PARITY}_n) = \mathrm{D}^{\mathrm{na}}(\mathrm{PARITY}_n) = n\)
-
\(\widetilde{\deg}_+(\mathrm{PARITY}_n) = \widetilde{\deg}(\mathrm{PARITY}_n) = n\)
-
\(\mathrm{UC}_{\min}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{C}_{\min}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{rank}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{sdeg}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{ardeg}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{PostQ}(\oplus_n) = \Theta(n) = \Theta(\log_2 \mathrm{DTsize}(\oplus_n))\)
-
\(\mathrm{cjdeg}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{I}_1(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n)\)
-
\(\mathrm{D}^{\mu}(\oplus_n) = n = \log_2 \mathrm{DTsize}(\oplus_n) \ \text{ under uniform } \mu\)
-
\(\deg(\mathrm{PARITY}_n) = n \text{ while } \deg_2(\mathrm{PARITY}_n) = 1\)
-
\(\mathrm{Adv}(\oplus_n) = \Theta(n) = \Theta\big(\mathrm{fbs}(\oplus_n)\big)\)
-
\(\mathrm{CG}(\oplus_n) = \Theta(n^2) = \Theta(\mathrm{EC}(\oplus_n)^2)\)
-
\(\mathrm{CG}(\oplus_n) = \Theta(n^2) = \Theta(\mathrm{C}(\oplus_n)^2)\)
-
\(\mathrm{CG}(\oplus_n) = \Theta(n^2) = \Theta(\mathrm{D}(\oplus_n)^2)\)
-
\(\mathrm{CG}(\oplus_n) = \Theta(n^2) = \Theta(\mathrm{R}_0(\oplus_n)^2)\)
-
\(\mathrm{D}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{DTsize}(\oplus_n) = 2^n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{s}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{s}^0(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{s}^1(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{bs}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{fbs}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{C}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{C}^0(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{C}^1(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{C}_{\min}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{UC}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{UC}_{\min}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{SP}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{RC}(\oplus_n) = \lceil n/2\rceil \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{EC}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{D}^{\mathrm{prod}}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{FC}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{bs}^0(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{bs}^1(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{rank}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{D}^{\mathrm{na}}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{R}_{\varepsilon}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{R}_{0}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{R}^{1}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{RS}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\chi(g)(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\bar{\chi}(g)(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{LR}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{noisyR}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{R}^{*}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{N}_{p}(\oplus_n) = \Theta(n\log n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{CA}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{CG}(\oplus_n) = \Theta(n^2) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{CG}^{\mathrm{pub}}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{CG}^{*}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{CG}^{\mathrm{ns}}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{R}^{\mathrm{na}}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{Q}_{\varepsilon}(\oplus_n) = \lceil n/2 \rceil \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{Q}_{\mathrm{E}}(\oplus_n) = \lceil n/2 \rceil \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{Q}_{0}(\oplus_n) = \lceil n/2 \rceil \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{PostQ}_{\varepsilon}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{QC}(\oplus_n) = \Theta(\sqrt n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{NQ}(\oplus_n) = \lceil n/2 \rceil \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{Q}^{\mathrm{rob}}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{Adv}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{Adv}^{\pm}(\oplus_n) = \Theta(\lceil n/2 \rceil) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\gamma_2^{\alpha}(\oplus_n) = \Theta(\lceil n/2 \rceil) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{MAdv}(\oplus_n) = n/2 \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\lambda(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\deg(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\widetilde{\deg}_{\varepsilon}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{sdeg}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{rdeg}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{rdeg}_{\varepsilon}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{ndeg}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\deg_p(\oplus_n) = n \ (p\ \text{odd}) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\deg_p(\oplus_n) = n \ (p\ \text{odd}) \to \infty, \qquad \mathrm{MaxInf}(\oplus_n) = 1\)
-
\(\mathrm{cjdeg}_{\varepsilon}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\widetilde{\deg}_{+}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{I}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{I}^{1}(\oplus_n) = n \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{prt}_{\varepsilon}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) vs \(\mathrm{NS}_{\delta}(f)\) total No bound exists open →\(\overline{\mathrm{prt}}_{\varepsilon}(\oplus_n) = \Theta(n) \to \infty, \qquad \mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12\)
-
\(\mathrm{NS}_{\delta}(\oplus_n) = \tfrac12\big(1-(1-2\delta)^n\big) \to \tfrac12, \qquad \mathrm{Stab}_{\rho}(\oplus_n) = \rho^{\,n} \to 0\)
-
\(\mathrm{MaxInf}(\oplus_n) = 1, \qquad \mathrm{Stab}_{\rho}(\oplus_n) = \rho^{\,n} \to 0\)
-
\(\mathrm{MaxInf}(\oplus_n) = 1, \qquad \mathrm{NS}_\delta(\oplus_n) \to \tfrac12\)
-
\(\mathrm{Q}(\mathrm{PARITY}_n)=\Omega(\mathrm{QS}_{\mathrm{weak}}(\mathrm{PARITY}_n)^2)\)
-
\(\mathrm{Q}(\mathrm{PARITY}_n)=\Omega(\mathrm{QS}_{\mathrm{str}}(\mathrm{PARITY}_n)^2)\)
-
\(\mathrm{Q}_{\varepsilon}(f)\) vs \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) total Gap open →\(\mathrm{Q}(\mathrm{PARITY}_n)=\Omega(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(\mathrm{PARITY}_n)^2)\)
-
\(\mathrm{Q}_{\varepsilon}(f)\) vs \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) total Gap open →\(\mathrm{Q}(\mathrm{PARITY}_n)=\Omega(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(\mathrm{PARITY}_n)^2)\)