\(\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
| 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 | \(\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.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{s}^1(f) = 1\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = n+1\) against \(\mathrm{C}^1(f) = 1\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = n\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{s}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^1(f_n) = O(1)\)from \(\mathrm{s}(f) = n\) against \(\mathrm{bs}^1(f) = 1\)
-
\(\mathrm{s}^0(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{s}^0(f) = n\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{bs}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{bs}(f) = n\) against \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{fbs}(f_n) \to \infty \ \text{ while } \ \mathrm{NQ}(f_n) = O(1)\)from \(\mathrm{fbs}(f) = n\) against \(\mathrm{NQ}(f) = 1\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{C}(f) = n\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{C}^0(f) = n\) against \(\mathrm{rdeg}_{\varepsilon}(f) = 1\)
-
\(\mathrm{UC}(f_n) \to \infty \ \text{ while } \ \mathrm{ndeg}(f_n) = O(1)\)from \(\mathrm{UC}(f) = n\) against \(\mathrm{ndeg}(f) = 1\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \widetilde{\deg}_{+}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = n\) against \(\widetilde{\deg}_{+}(f) = 1\)
-
\(\mathrm{SP}(f_n) \to \infty \ \text{ while } \ \mathrm{osss}(f_n) = O(1)\)from \(\mathrm{SP}(f) = n\) against \(\mathrm{osss}(f) = 2(1-2^{-n})\)
-
\(\mathrm{RC}(f_n) \to \infty \ \text{ while } \ \hat{L}_1(f_n) = O(1)\)from \(\mathrm{RC}(f) = \Theta(n)\) against \(\hat{L}_1(f) = 3 - 2^{2-n}\)
-
\(\mathrm{spar}(f_n) = 2^{\Omega(\mathrm{EC}(f_n))}\)from \(\mathrm{spar}(f) = 2^n\) against \(\mathrm{EC}(f) = n\)
… and 2857 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{C} = \Theta(\mathrm{Q}^2)$ -- the "$2$" in the C-vs-Q cell (usually quoted with AND).
-
$\deg = \Theta(\widetilde{\deg}^2)$, matching the ABKRT upper bound $\deg = O(\widetilde{\deg}^2)$.
-
$\mathrm{s} = \lambda^2$, matching $\mathrm{s} \le \lambda^2$.
-
$\mathrm{bs} = \lambda^2$; improved to $\lambda^{2.127}$ by Meiburg.
-
Maximal gap between $\mathrm{ndeg}(f)=1$ and $\mathrm{ndeg}(\bar f)=n$.
Cited as a witness by
-
\(\mathrm{SP}(\vee_n) = \mathrm{D}(\vee_n) = n\)
-
\(\mathrm{bs}(\mathrm{OR}_n) = n = \Theta(\widetilde{\deg}(\mathrm{OR}_n)^2)\)
-
\(\deg(\mathrm{OR}_n) = n = \Theta(\widetilde{\deg}(\mathrm{OR}_n)^2)\)
-
\(\mathrm{bs}(\vee_n) = n = \mathrm{Adv}(\vee_n)^2\)
-
\(\deg_2(\mathrm{OR}_n) = n = \log_2 \mathrm{spar}(\mathrm{OR}_n)\)
-
\(\mathrm{CA}(\vee_n) = \Theta(n) = \Theta(\mathrm{cbs}(\vee_n))\)
-
\(\mathrm{prt}(\vee_n) = \Theta(n) = \Theta(\mathrm{cbs}(\vee_n))\)
-
\(\mathrm{rprt}(\vee_n) = \Theta(n) = \Theta(\mathrm{cbs}(\vee_n))\)
-
\(\mathrm{CA}(\vee_n) = \Theta(n) = \Theta(\mathrm{psD}(\vee_n))\)
-
\(\mathrm{prt}(\vee_n) = \Theta(n) = \Theta(\mathrm{psD}(\vee_n))\)
-
\(\mathrm{rprt}(\vee_n) = \Theta(n) = \Theta(\mathrm{psD}(\vee_n))\)
-
\(\mathrm{Q}_\varepsilon(\mathrm{OR}_N) = \Theta\big(\sqrt{N\log(1/\varepsilon)}\big)\)
-
\(\mathrm{Q}_0(\mathrm{OR}_n) = \mathrm{Q}_E(\mathrm{OR}_n) = n\)
-
\(\mathrm{bs}(\mathrm{OR}_n) = \mathrm{fbs}(\mathrm{OR}_n) = n\)
-
\(\mathrm{fbs}(\mathrm{OR}_n) = \mathrm{C}(\mathrm{OR}_n) = n\)
-
\(\mathrm{fbs}(\mathrm{OR}_n) = n = \Theta(\mathrm{R}(\mathrm{OR}_n))\)
-
\(\mathrm{RC}(\mathrm{OR}_n) = n = \Theta\big(\widetilde{\deg}(\mathrm{OR}_n)^2\big)\)
-
\(\mathrm{s}(\mathrm{OR}_n) = \mathrm{bs}(\mathrm{OR}_n) = n\)
-
\(\mathrm{bs}(\mathrm{OR}_n) = \mathrm{C}(\mathrm{OR}_n) = n\)
-
\(\mathrm{Q}_E(\mathrm{OR}_n) = n = \mathrm{D}(\mathrm{OR}_n)\)
-
\(\mathrm{FC}(\mathrm{OR}_n) = \mathrm{EC}(\mathrm{OR}_n) = n\)
-
\(\mathrm{bs}^0(\mathrm{OR}_n) = \mathrm{bs}(\mathrm{OR}_n) = n\)
-
\(\mathrm{bs}(\mathrm{OR}_n) = n,\quad \mathrm{bs}^1(\mathrm{OR}_n) = 1\)
-
\(\mathrm{s}^0(\mathrm{OR}_n) = \mathrm{bs}^0(\mathrm{OR}_n) = n\)
-
\(\mathrm{cbs}(\vee_n) = n = \Theta(\mathrm{R}(\vee_n))\)
-
\(\mathrm{rank}(\mathrm{OR}_n) = 1,\quad \mathrm{D}(\mathrm{OR}_n) = n\)
-
\(\widetilde{\deg}(\mathrm{OR}_n) = \Theta(\sqrt n),\quad \widetilde{\deg}_+(\mathrm{OR}_n) = 1\)
-
\(\mathrm{sdeg}(\mathrm{OR}_n) = \widetilde{\deg}_+(\mathrm{OR}_n) = 1\)
-
\(\mathrm{CG}^{*}(\mathrm{OR}_n) = \Theta(n) \text{ while } \mathrm{Q}(\mathrm{OR}_n) = \Theta(\sqrt n)\)
-
\(\mathrm{CG}^{\mathrm{pub}}(\vee_n) = \Theta(n) = \Theta(\mathrm{CA}(\vee_n))\)
-
\(\mathrm{CA}(\vee_n) = \Theta(n) = \Theta(\mathrm{CG}^{\mathrm{pub}}(\vee_n))\)
-
\(\mathrm{CA}(\vee_n) = \Theta(n) = \Theta(\mathrm{fbs}(\vee_n))\)
-
\(\mathrm{fbs}(\vee_n) = n = \Theta(\mathrm{CA}(\vee_n))\)
-
\(\mathrm{fbs}(\vee_n) = n = \Theta\big(\mathrm{Adv}(\vee_n)^2\big)\)
-
\(\mathrm{CA}(\vee_n) = \Theta(n) = \Theta\big(\widetilde{\deg}(\vee_n)^2\big)\)
-
\(\mathrm{CA}(\vee_n) = \Theta(n) = \Theta\big(\mathrm{Adv}(\vee_n)^2\big)\)
-
\(\mathrm{R}_0(\vee_n) = n = \Theta(\mathrm{CG}(\vee_n))\)
-
\(\mathrm{D}(\vee_n) = n = \Theta(\mathrm{CG}(\vee_n))\)
-
\(\mathrm{DTsize}(\vee_n) = n+1 \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\mathrm{D}^{\oplus}(\vee_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\mathrm{UC}(\vee_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\mathrm{SP}(\vee_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\mathrm{D}^{\mathrm{prod}}(\vee_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\chi(g)(\vee_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\mathrm{N}_{p}(\vee_n) = \Theta(n) \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\mathrm{Adv}(\vee_n) = \Theta(\sqrt{n}) \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\deg_p(\vee_n) = n \to \infty, \qquad \mathrm{Stab}_{\rho}(\vee_n) \to 1\)
-
\(\mathrm{Stab}_{\rho}(\vee_n) \to 1, \qquad \mathrm{NS}_{\delta}(\vee_n) = 2^{1-n}\big(1-(1-\delta)^n\big) \to 0\)
-
\(\mathrm{Stab}_{\rho}(\vee_n) \to 1, \qquad \mathrm{MaxInf}(\vee_n) = 2^{1-n} \to 0\)