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

OR

The archetypal one-sided function: cheap 1-certificates, expensive 0-certificates.

total basic arity: $n$ bits— also: unstructured search (decision version), \vee

Description

$\mathrm{OR}_n(x) = 1$ iff some $x_i = 1$.

Formal definition

$$\mathrm{OR}_n : \{0,1\}^n \to \{0,1\},\qquad \mathrm{OR}_n(x) \;=\; \bigvee_{i=1}^n x_i \;=\; 1 - \prod_{i=1}^n (1-x_i).$$

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 \(\Theta(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 \(\Theta(\sqrt{n})\) Grover upper bound, BBBV lower bound. Exactly $\tfrac{\pi}{4}\sqrt n$ asymptotically. Grover96 BBBV97
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(n\) BBCMdW01
\(\deg(f)\) Exact degree \(n\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\sqrt{n})\) NS94 Paturi92
\(\mathrm{sdeg}(f)\) Sign degree \(1\) A linear threshold function: $\sum_i x_i \ge 1$.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(1\) $p(x)=\sum_i x_i$ vanishes exactly on $\mathrm{OR}^{-1}(0)$.
\(\mathrm{rdeg}(f)\) Rational degree \(n\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\} = \max\{1, n\}$. IJKKKSWW23
\(\mathrm{s}^0(f)\) 0-sensitivity \(n\)
\(\mathrm{s}^1(f)\) 1-sensitivity \(1\)
\(\mathrm{s}(f)\) Sensitivity \(n\)
\(\mathrm{bs}(f)\) Block sensitivity \(n\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(n\)
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n\)
\(\mathrm{C}^1(f)\) 1-certificate complexity \(1\)
\(\mathrm{C}(f)\) Certificate complexity \(n\)
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\)
\(\lambda(f)\) Spectral sensitivity \(\sqrt{n}\) Sensitivity graph is a star $K_{1,n}$ plus isolated edges; $\|K_{1,n}\| = \sqrt n$. ABKRT21
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(n\)
\(\mathrm{I}(f)\) Total influence (L2 influence) \(n\,2^{1-n}\) Vanishingly small: OR is very noise-stable.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(n)\)· Constant-rate noise costs only a constant factor here, unlike PARITY. FRPU94
\(\mathrm{FC}(f)\) Fractional certificate complexity \(n\) Equal to $\mathrm{fbs}$ by LP duality; the LP is integral here because at $0^n$ every coordinate must carry weight $1$. Aaronson08
\(\mathrm{EC}(f)\) Expectational certificate complexity \(n\) Sandwiched between $\mathrm{fbs}=n$ and $\mathrm{C}=n$. GJKKLSSV17
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(n\)
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(1\)
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(1\) Any $1$-input is certified by a single $1$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n\) At least $\mathrm{C}=n$; and the "first $1$" family -- $x_1=\cdots=x_{i-1}=0,\,x_i=1$ for each $i$, together with $0^n$ -- is unambiguous with all certificates of size $\le n$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(n\) putative Corrected. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is the one-sided version, not a minimum over inputs. $\mathrm{UC}^0 = n$ because $0^n$ is the only $0$-input and its certificate must fix every bit. $\mathrm{UC}^1 = n$ too: an unambiguous $1$-cover partitions the $2^n-1$ ones-inputs into subcubes of sizes $2^{n-c_i}$, and an odd total forces some $c_i = n$. Consistent with the two general bounds $\mathrm{D} \le \mathrm{UC}_{\min}^2$ and $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17], both of which the old value $1$ violated. BHT17
\(\mathrm{SP}(f)\) Subcube partition complexity \(n\) The subcube containing $0^n$ must fix all $n$ coordinates, since any free coordinate could be set to $1$; the "first $1$" tree achieves codimension $n$.
\(\mathrm{rank}(f)\) Decision tree rank \(1\) The "first $1$" tree is a caterpillar -- every internal node has a leaf child -- and rank $0$ would mean $f$ is constant.
\(\mathrm{DTsize}(f)\) Decision tree size \(n+1\) The caterpillar has $n+1$ leaves. Conversely the unique $0$-input sits at depth $n$ in any tree, and each of the $n$ branches leaving that path reaches a different leaf.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Every variable is relevant.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) A fixed distribution over query sets of size $m$ leaves some coordinate unqueried with probability $\ge 1-m/n$, and $0^n$ versus $e_i$ is then undecidable; so $m=\Omega(n)$.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(n)\) By Theorem 8, $\mathrm{noisyR}^{\mathrm{na}} = \Theta(\mathrm{R}^{\mathrm{na}})$ for every partial Boolean function. Buying $n$ coordinates at bias $\gamma$ costs $n\gamma^2$, and distinguishing $0^n$ from a random $e_i$ needs $\gamma = \Omega(1)$ on the special coordinate, which a non-adaptive schedule cannot aim at. BenDavidBlais20composition
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) Quantum certificate complexity is $\Theta(\sqrt{\mathrm{RC}})$; for OR this is the Grover-verification bound. Aaronson08
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg}(\mathrm{OR})=1$. deWolf03
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) Zero error costs the full $n$: the $\Theta(\sqrt n)$ of Grover is bought entirely with bounded error [BCWZ99]. The polynomial route gives the same thing -- not through $\deg/2$, which is a $\mathrm{Q}_{\mathrm{E}}$ floor, but through $\mathrm{rdeg}/2$: certifying $\mathrm{OR} = 0$ needs the degree-$n$ polynomial $\prod_i(1-x_i)$, so $\mathrm{ndeg}(\bar f) = n$ and $\mathrm{Q}_0 \ge n/2$. BCWZ99
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(1\) $p(x)=\sum_i x_i$ is $0$ at the unique $0$-input and $\ge 1$ at every $1$-input. The extreme case of one-sided approximation being cheaper than two-sided ($\widetilde{\deg}=\Theta(\sqrt n)$). BT22
\(\deg_2(f)\) Mod-2 degree \(n\) Over $\mathbb{F}_2$, $\mathrm{OR}=1-\prod_i(1-x_i)$ contains the monomial $x_1\cdots x_n$.
\(\mathrm{spar}(f)\) Fourier sparsity \(2^n\) In the $\pm1$ encoding $(-1)^{\mathrm{OR}(x)} = -1 + 2^{1-n}\prod_i(1+\chi_i)$, so every one of the $2^n$ characters has a nonzero coefficient.
\(\hat{L}_1(f)\) Spectral norm \(3 - 2^{2-n}\) From the same expansion: $|-1+2^{1-n}| + (2^n-1)\,2^{1-n}$. The spectral norm of OR is below $3$ for every $n$ -- a useful reminder that $\hat L_1$ is not a proxy for query complexity. ODonnell14
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(n\) The Fourier support is all of $2^{[n]}$, whose $\mathbb{F}_2$-span is everything.
\(\mathrm{MaxInf}(f)\) Maximum influence \(2^{1-n}\) By symmetry every coordinate has influence $\mathrm{I}(f)/n = 2^{1-n}$.
\(\mathrm{Var}(f)\) Variance \(2^{2-n}(1-2^{-n})\) Exactly $4p(1-p)$ with $p = 2^{-n}$. Exponentially unbalanced, which is why every raw Fourier quantity on this page is tiny while $\mathrm{D} = n$: they are all measuring the bias, not the difficulty.
\(\mathrm{osss}(f)\) OSSS number \(2(1-2^{-n})\) putative Exactly $4p(1-p)/(2p) = 2(1-p)$, since $\mathrm{MaxInf} = 2p$. The OSSS bound certifies two queries against $\mathrm{D} = n$: dividing out the bias fixes the units but cannot make a one-coordinate statistic see a global obstruction. See Dimensionless quantities and how to normalize them.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(n)\) putative $\mathrm{NS}_\delta = 2^{1-n}(1-(1-\delta)^n)$ crosses $\mathrm{Var}/4 = 2^{-n}(1-2^{-n})$ at $(1-\delta)^n = \tfrac12(1+2^{-n})$, i.e. $\delta^{*} = (\ln 2)/n\,(1+o(1))$. Tight against $\mathrm{nsr} \le 4\mathrm{s} = 4n$: an OR tolerates as much noise as anything on $n$ relevant variables can.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(2^{1-n}\big(1-(1-\delta)^n\big)\) Exact, for every $\delta$: $\vee_n(x) \ne \vee_n(y)$ holds precisely when exactly one of $x, y$ is $0^n$, and $\Pr[x = 0^n,\ y \ne 0^n] = 2^{-n}(1-(1-\delta)^n)$. So $\vee_n$ is exponentially noise-stable -- the extreme opposite of \(\oplus_n\).
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - 2^{2-n}\big(1-(\tfrac{1+\rho}{2})^n\big)\) From $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the entry above. Tends to $1$ for every fixed $\rho$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) At most $\mathrm{R}=\Theta(n)$. For the lower bound, take the sabotaged input with a single $\ast$ and zeros elsewhere: the value is undetermined, and finding the $\ast$ among $n$ positions needs $\Omega(n)$ queries. BenDavidKothari18
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CA}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(n)$ and $\mathrm{fbs}(f) = n$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(n)$ 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(\sqrt{n})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\sqrt{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(\sqrt{n})$ here.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(\sqrt{n})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt{n})$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\sqrt n)\) $\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} = \Theta(\sqrt n)$. 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 $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}^0(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}^0(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: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(n)\) Sandwiched by the [CGLMSG23] bounds $\max\{\mathrm{Adv}^2, \mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$: here $\mathrm{Adv}^2 = \Theta(n)$ and $\mathrm{R}_0 = n$ from below, and the asymmetric product $\mathrm{C}^0\mathrm{C}^1 = n \cdot 1$ from above. OR is one of the two functions on which the certificate-product bound is tight. Note that the old reading $\mathrm{CG} \le \mathrm{D}$ is not available in general -- $\mathrm{CG}$ is not bounded by the arity -- it just happens to hold here. CGLMSG23
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(1\) The single rational function $r(x) = \dfrac{n\sum_i x_i}{1 + n\sum_i x_i}$ has numerator and denominator of degree $1$, is $0$ at $0^n$, and is $\ge \tfrac{n}{n+1} \ge \tfrac23$ at every $1$-input. So one degree of freedom suffices where $\widetilde{\deg} = \Theta(\sqrt n)$ is needed for polynomials -- the cleanest illustration that rational approximation is a strictly different resource. MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$, and $\mathrm{rdeg}_\varepsilon(\mathrm{OR}) = 1$. Postselection makes unstructured search free: prepare a uniform superposition, query once, and postselect on the answer bit being $1$. MahadevdeWolf15 Aaronson05postbqp
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(\sqrt n)\) Robust Grover: search over bounded-error inputs costs $O(\sqrt n)$ with no log factor, by amplitude amplification around a subroutine whose error is never amplified. Classically, noisy OR costs $\Theta(n)$ either way, so the quantum speedup survives noise intact. HoyerMoscadeWolf03 BNRdW05
\(\deg_p(f)\) Mod-p degree \(n\) For every prime $p$. Over $\mathbb{F}_p$ the multilinear representation is still $1 - \prod_i(1 - x_i)$, which contains $x_1\cdots x_n$ with coefficient $(-1)^{n+1} \ne 0$. Unlike \(\oplus_n\), OR gets no help from small characteristic -- which is why the value can be recorded as a bare $n$ with no choice of $p$ to make.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) Take the product distribution with each bit $1$ independently with probability $1/n$. After seeing $m$ zeros the conditional probability that a $1$ remains is $1 - (1-1/n)^{n-m}$, which is $\ge 1 - e^{-1/2} > 0.39$ for $m \le n/2$; so no depth-$n/2$ tree has error $\le 1/3$. Product distributions are already as hard as OR gets, which is not true for every function.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Sandwiched: $\mathrm{s}(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{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) By Yao's minimax principle $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$. A concrete maximiser: half the mass on $0^n$, the other half spread uniformly over the $n$ weight-one inputs. A depth-$d$ tree that has seen only zeros is consistent with $0^n$ and with the $n-d$ unqueried $e_i$, so whichever answer it commits to it errs on mass at least $\min\{1/2,\ (n-d)/(2n)\}$, forcing $d \ge n/3$. See \(\mathrm{D}^{\mathrm{prod}}(f)\) for the product-distribution version. Yao77
\(\mathrm{I}^{1}(f)\) Total L1 influence \(n\,2^{1-n}\) Boolean-valued, so the $L_1$ and $L_2$ total influences coincide: this is the $\mathrm{I}(f)$ recorded above.
\(\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)$, attained at $0^n$. The measure only says something new for search problems where some input has several valid answers. 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)$. Contrast the relation \(\mathrm{ApproxHW}\), where $\mathrm{R} = O(1)$ but $\mathrm{psD} = \Omega(n)$ [CDM23]. CDM23
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(n)\)· putative Upper: $\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f) = n$, the $1$-leaves of the caterpillar being disjoint conjunctions. Lower: let $h = \sum_C \alpha_C C$ be a width-$d$ conical junta with $|h - \vee_n| \le 1/3$ pointwise. A conjunction with $C(e_i) = 1$ either has all its literals negative -- and then $C(0^n) = 1$ as well -- or has exactly one positive literal, necessarily $x_i$. Conjunctions of the first kind contribute at most $h(0^n) \le 1/3$ to each of the $n$ points $e_i$, so writing $A$ for the total weight of the conjunctions with exactly one positive literal, $2n/3 \le \sum_i h(e_i) \le n/3 + A$, i.e. $A \ge n/3$. Now evaluate under the product measure that sets each bit to $1$ with probability $1/d$: each such $C$ has expectation at least $\tfrac1d(1-\tfrac1d)^{d-1} \ge \tfrac{1}{ed}$, while $\mathbb{E}[h] \le 4/3$, so $A \le 4ed/3$ and $d \ge n/(4e)$. Non-negativity therefore costs a quadratic blow-up over $\widetilde{\deg} = \Theta(\sqrt n)$.
\(\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 \(n\) Exactness on the other 2^n−1 cube inputs forces the degree-n point-indicator polynomial, while the singleton input has a nonzero error gap. KLLPV26
\(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) Bounded polynomial degree with error on 1-inputs \(\Theta(\sqrt n)\) The Grover acceptance polynomial is exact on the singleton output class; approximate degree gives the matching √n floor. 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. 2871 in total, strongest first.

… and 2857 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