\(\mathrm{AND}_n\)
AND
The dual of OR; the witness cited in most "$2,2$" and "$2,4$" cells of the total-function matrix.
total
basic
arity: $n$ bits— also: \wedge
Description
$\mathrm{AND}_n(x)=1$ iff every $x_i=1$. All measures are those of $\mathrm{OR}_n$ with the roles of $0$ and $1$ exchanged.
Formal definition
$$\mathrm{AND}_n : \{0,1\}^n \to \{0,1\},\qquad \mathrm{AND}_n(x) = \prod_{i=1}^n x_i .$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic 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})\) | |
| \(\deg(f)\) Exact degree | \(n\) | |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Theta(\sqrt{n})\) | |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(1\) | |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(n\) | |
| \(\mathrm{s}(f)\) Sensitivity | \(n\) | |
| \(\mathrm{bs}(f)\) Block sensitivity | \(n\) | |
| \(\mathrm{C}(f)\) Certificate complexity | \(n\) | |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(n)\) | |
| \(\lambda(f)\) Spectral sensitivity | \(\sqrt{n}\) | IJKKKSWW23 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(n\) | |
| \(\mathrm{rdeg}(f)\) Rational degree | \(n\) | |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(n\) | |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(n\) | Exact quantum computation gives no speedup, as for OR. BBCMdW01 |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(1\) | |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(n\) | |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(1\) | |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(n\) | |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(n\) | |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(n\) | |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(n\) | Sandwiched between $\mathrm{fbs}=n$ and $\mathrm{C}=n$. GJKKLSSV17 |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(1\) | Any $0$-input is certified by a single $0$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(n\) | The "first $0$" family, mirroring OR. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(n\) putative | Corrected, mirroring \(\mathrm{OR}_n\): $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is one-sided, not a minimum over inputs. $\mathrm{UC}^1 = n$ since $1^n$ is the only $1$-input, and $\mathrm{UC}^0 = n$ since an unambiguous $0$-cover partitions an odd number ($2^n-1$) of inputs into subcubes. The old value $1$ violated both $\mathrm{D} \le \mathrm{UC}_{\min}^2$ and $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17]. BHT17 |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(n\) | The subcube containing $1^n$ must fix everything. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(1\) | Caterpillar tree: query the bits in order and stop at the first $0$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(n+1\) | Mirror of OR: the caterpillar has $n+1$ leaves and no tree has fewer. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n\) | Every variable is relevant. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(\sqrt n)\) | Aaronson08 |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\lceil n/2 \rceil\) | $\mathrm{ndeg}(\mathrm{AND})=n$. deWolf03 |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(n)\) | Between $\mathrm{rdeg}/2 = n/2$ (here $\mathrm{ndeg}(f) = n$, the monomial $x_1\cdots x_n$) and $\mathrm{D} = n$, exactly as for \(\mathrm{OR}_n\). BCWZ99 |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(\Theta(\sqrt n)\) putative | Unlike OR, the one-sided relaxation buys nothing: a polynomial bounded by $1/3$ on all of $\{0,1\}^n\setminus\{1^n\}$ and at least $2/3$ at $1^n$ still needs degree $\Omega(\sqrt n)$ by the Markov-brothers argument, and Chebyshev gives $O(\sqrt n)$. NS94 BT22 |
| \(\mathrm{spar}(f)\) Fourier sparsity | \(2^n\) | $(-1)^{\mathrm{AND}(x)} = 1 - 2^{1-n}\prod_i(1-\chi_i)$: every character appears. |
| \(\hat{L}_1(f)\) Spectral norm | \(3 - 2^{2-n}\) | Same computation as for OR. ODonnell14 |
| \(\dim_{\mathbb{F}_2}(f)\) Fourier dimension | \(n\) | The Fourier support spans all of $\mathbb{F}_2^n$: it contains every singleton. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(n\,2^{1-n}\) | |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(2^{1-n}\) | |
| \(\mathrm{Var}(f)\) Variance | \(2^{2-n}(1-2^{-n})\) | $4p(1-p)$ at $p = 1-2^{-n}$; identical to \(\mathrm{OR}_n\) by De Morgan, which flips $p$ to $1-p$ and leaves $\mathrm{Var}$ alone. |
| \(\mathrm{osss}(f)\) OSSS number | \(2(1-2^{-n})\) putative | Identical to \(\mathrm{OR}_n\): complementing the input and the output changes neither $\mathrm{Var}$ nor $\mathrm{MaxInf}$. |
| \(\mathrm{nsr}(f)\) Noise robustness | \(\Theta(n)\) putative | Identical to \(\mathrm{OR}_n\) by De Morgan; $\delta^{*} = (\ln 2)/n\,(1+o(1))$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(n)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{CA}(f) \le \mathrm{RC}(f)$, with $\mathrm{fbs}(f) = n$ and $\mathrm{RC}(f) = \Theta(n)$ here. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(n)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{RC}(f)$, with $\mathrm{fbs}(f) = n$ and $\mathrm{RC}(f) = \Theta(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{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here. |
| \(\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. |
| \(\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 | \(n\) | Sandwiched: $\mathrm{C}^1(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\chi(f)\) Conflict complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}^1(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}^1(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(n)\) | Sandwiched: $\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 $\mathrm{C}^0\mathrm{C}^1 = 1 \cdot n$ from above. The mirror image of \(\mathrm{OR}_n\). CGLMSG23 |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(\sqrt{n})\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt{n})$ here. |
| \(\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\) | Dual to \(\mathrm{OR}_n\): $1 - r(\bar x)$ for the same degree-$1$ rational $r$. MahadevdeWolf15 |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(1)\) | Dual to \(\mathrm{OR}_n\). MahadevdeWolf15 |
| \(\deg_p(f)\) Mod-p degree | \(n\) | For every prime $p$: $\mathrm{AND} = \prod_i x_i$ over every field, so there is no choice of $p$ to make and the value is a bare $n$. |
| \(\deg_2(f)\) Mod-2 degree | \(n\) | The $p=2$ case of the line above: $\mathrm{AND} = x_1\cdots x_n$ over $\mathbb{F}_2$. |
| \(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity | \(n\) putative | Parity queries are unaffected by complementing the input (a parity of a set shifts by a constant), so $\mathrm{D}^{\oplus}(\mathrm{AND}_n) = \mathrm{D}^{\oplus}(\mathrm{OR}_n) = n$. |
| \(\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 | \(\min\{n,\ \lceil \log(1/\varepsilon)/\log(1/p)\rceil\} \text{ under } \mu_p\) | The cleanest illustration of why $\mathrm{D}^{\mu}$ is a family of measures rather than one number. Let $\mu_p$ make each bit $1$ independently with probability $p$. Querying bits until one comes up $0$ and answering $1$ if the first $m$ are all $1$ errs with probability $p^{m}(1-p^{n-m})$, so $m = \lceil \log(1/\varepsilon)/\log(1/p)\rceil$ queries suffice; conversely, the leaf reached by the all-ones input has some depth $m_0 \le m$ and carries $\mathrm{AND}^{-1}(0)$-mass $p^{m_0} - p^{n}$ against $\mathrm{AND}^{-1}(1)$-mass $p^{n}$, so the error is at least $\min\{p^{m}-p^{n},\,p^{n}\}$. At $p = 1/2$ this is $\Theta(\log(1/\varepsilon))$; at $p = 1 - 1/n$ it is $n$. Averaging over the parameter is exactly what the zoo cannot do, which is why $\mathrm{D}^{\mu}$ is left out of the ladder ordering on the matrix page. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(n\) | Take $p = 1-1/n$ in the previous line: $\log(1/p) = \Theta(1/n)$, so the bound saturates at $n$. Product distributions are already worst-case-hard for AND. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(1\) | $\mathrm{AND}_n = \operatorname{sign}\big(\sum_i x_i - n + \tfrac12\big)$: every halfspace has threshold degree $1$. Against $\widetilde{\deg} = \Theta(\sqrt n)$ and $\deg = n$. |
| \(\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{NS}_{\delta}(f)\) Noise sensitivity | \(2^{1-n}\big(1-(1-\delta)^n\big)\) | Exact, for every $\delta$: $\wedge_n(x) \ne \wedge_n(y)$ holds precisely when exactly one of $x,y$ equals $1^n$, and $\Pr[x = 1^n,\ y \ne 1^n] = 2^{-n}(1-(1-\delta)^n)$. The mirror of \(\mathrm{OR}_n\) under $x \mapsto \bar x$: exponentially noise-stable. |
| \(\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{N}_{p}(f)\) Noisy decision tree complexity | \(\Theta(n)\)· | Noisy decision trees are unaffected by negating input bits or complementing the output, and $\wedge_n(x) = \lnot\vee_n(\bar x)$, so this is the \(\mathrm{OR}_n\) value: constant-rate noise costs only a constant factor, unlike \(\oplus_n\). FRPU94 |
| \(\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 ones elsewhere: the value is undetermined, and finding the $\ast$ among $n$ positions needs $\Omega(n)$ queries. BenDavidKothari18 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Theta(\sqrt n)\) | Robust Grover search for a zero costs $O(\sqrt n)$ with no log factor, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt n)$. The \(\mathrm{OR}_n\) entry after negating the input bits. HoyerMoscadeWolf03 BNRdW05 |
| \(\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 $1^n$. GoosPitassi14 |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(n)\) | Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Theta(n)\)· putative | Upper: $\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f) = n$. Lower: let $h = \sum_C \alpha_C C$ be a width-$d$ conical junta with $|h - \wedge_n| \le 1/3$ pointwise. The conjunctions that evaluate to $1$ at $1^n$ are exactly the all-positive ones, so $\sum_{C \text{ positive}} \alpha_C = h(1^n) \ge 2/3$; an all-positive $C$ still evaluates to $1$ at $1^n - e_i$ unless $x_i$ is one of its at most $d$ literals, whence $\sum_i h(1^n - e_i) \ge \sum_{C \text{ positive}} \alpha_C\,(n - |C|) \ge (n-d)\tfrac23$. Every $1^n - e_i$ is a $0$-input, so the left-hand side is at most $n/3$, giving $d \ge n/2$. Non-negativity thus wipes out the $\widetilde{\deg} = \Theta(\sqrt n)$ saving, and it does so even though $\mathrm{sdeg}(\wedge_n) = 1$. |
| \(\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(\sqrt n)\) | The Grover acceptance polynomial is exact on the singleton output class; approximate degree gives the matching √n floor. KLLPV26 |
| \(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) Bounded polynomial degree with error on 1-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 |
| \(\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. 656 in total, strongest first.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{s}^0(f) = 1\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^0(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = n+1\) against \(\mathrm{C}^0(f) = 1\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = n\) against \(\mathrm{bs}^0(f) = 1\)
-
\(\mathrm{s}^1(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{s}^1(f) = n\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{C}^1(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{C}^1(f) = n\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{bs}^1(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{bs}^1(f) = n\) against \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{NQ}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{NQ}(f) = \lceil n/2 \rceil\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\mathrm{ndeg}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{ndeg}(f) = n\) against \(\mathrm{rdeg}_{\varepsilon}(f) = 1\)
-
\(\widetilde{\deg}_{+}(f_n) \to \infty \ \text{ while } \ \mathrm{osss}(f_n) = O(1)\)from \(\widetilde{\deg}_{+}(f) = \Theta(\sqrt n)\) against \(\mathrm{osss}(f) = 2(1-2^{-n})\)
-
\(\mathrm{s}(f_n) = \Omega\big(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f_n)^{2}\big)\)from \(\mathrm{s}(f) = n\) against \(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f) = \Theta(\sqrt n)\)
-
\(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\) total pair →\(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f_n) = \Omega\big(\mathrm{Q}_{\varepsilon}(f_n)^{2}\big)\)from \(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f) = n\) against \(\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^0(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{C}^0(f) = 1\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = n+1\) against \(\mathrm{s}^0(f) = 1\)
-
\(\mathrm{s}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{s}(f) = n\) against \(\mathrm{bs}^0(f) = 1\)
… and 642 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{C}(f)=n$, $\mathrm{Q}(f)=\Theta(\sqrt n)$: the quadratic C-vs-Q separation.
-
$\mathrm{bs}=\lambda^2$.
-
$\mathrm{RC}=\Theta(\mathrm{Q}^2)$, matching $\mathrm{RC}=O(\mathrm{Q}^2)$.
-
$\deg = \Theta(\widetilde{\deg}^2)$.
Cited as a witness by
-
\(\deg(\wedge_n) = n = \lambda(\wedge_n)^2\)
-
\(\deg(\mathrm{AND}_n) = n = \Theta(\mathrm{Q}(\mathrm{AND}_n)^2)\)
-
\(\sqrt{\mathrm{s}(f)} \le \lambda(f)\)
-
\(\mathrm{I}(f) \text{ can be exponentially smaller than } \mathrm{s}(f)\)
-
\(\deg_2(\mathrm{AND}_n) = \mathrm{D}^{\oplus}(\mathrm{AND}_n) = n\)
-
\(\deg_2(\mathrm{AND}_n) = \deg(\mathrm{AND}_n) = n\)
-
\(\mathrm{C}^{1}(\wedge_n) = \mathrm{cbs}(\wedge_n) = n\)
-
\(\mathrm{C}^{1}(\wedge_n) = n = \Theta(\mathrm{psD}(\wedge_n))\)
-
\(\mathrm{bs}(\mathrm{AND}_n) = n,\quad \mathrm{bs}^0(\mathrm{AND}_n) = 1\)
-
\(\mathrm{bs}^1(\mathrm{AND}_n) = \mathrm{bs}(\mathrm{AND}_n) = n\)
-
\(\mathrm{s}^1(\mathrm{AND}_n) = \mathrm{bs}^1(\mathrm{AND}_n) = n\)
-
\(\widetilde{\deg}_+(\mathrm{AND}_n) = \widetilde{\deg}(\mathrm{AND}_n) = \Theta(\sqrt n)\)
-
\(\widetilde{\deg}_+(\mathrm{AND}_n) = \Theta(\sqrt n),\quad \mathrm{sdeg}(\mathrm{AND}_n) = 1\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(\wedge_n) = n \ \text{under}\ \mu_{1-1/n} \to \infty, \qquad \mathrm{Stab}_{\rho}(\wedge_n) \to 1\)
-
\(\mathrm{NQ}(\wedge_n) = \lceil n/2 \rceil \to \infty, \qquad \mathrm{Stab}_{\rho}(\wedge_n) \to 1\)
-
\(\mathrm{ndeg}(\wedge_n) = \deg(\wedge_n) = n\)
-
\(\mathrm{ndeg}(\wedge_n) = \mathrm{C}^1(\wedge_n) = n\)
-
\(\mathrm{ndeg}(\wedge_n) = \mathrm{rdeg}(\wedge_n) = n\)