Q The Query Complexity Zoo
\(\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

MeasureValueNotes
\(\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.

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

Separations it witnesses

Cited as a witness by