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

AND-OR tree (depth 2)

$\mathrm{D}=\mathrm{R}=\Theta(N)$ while $\mathrm{C}=\mathrm{bs}=\sqrt N$; also separates sabotage and max-conflict from conflict complexity.

total composed arity: $N = n^2$ bits ($n$ blocks of $n$)— also: \wedge\circ\vee, CNF-like read-once formula of depth 2

Description

Split the input into $n$ blocks of $n$ bits. Output $1$ iff every block contains at least one $1$.

Formal definition

$$f(x^1,\dots,x^n) = \bigwedge_{j=1}^{n}\ \bigvee_{i=1}^{n} x^j_i, \qquad x^j\in\{0,1\}^n,\ N = n^2 .$$

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(N = n^2\)
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n^2)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n^2)\) SaksWigderson86 Snir85
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(n) = \Theta(\sqrt N)\) Robust quantum search: no log factor. HoyerMoscadeWolf03 BBBV97
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n^2)\) $\mathrm{Q}_E \ge \deg/2 = n^2/2$.
\(\deg(f)\) Exact degree \(n^2\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(n)\)
\(\mathrm{sdeg}(f)\) Sign degree \(\Omega(\sqrt n) = \Omega(N^{1/4})\) Minsky-Papert prove $\mathrm{sdeg}(\mathrm{AND}_m \circ \mathrm{OR}_b) = \Omega(\min\{m,\sqrt b\})$, which on the balanced tree ($m = b = n$) is $\Omega(\sqrt n)$. The often-quoted $\Theta(N^{1/3})$ belongs to the unbalanced \(\mathrm{MP}_m\) function $\mathrm{AND}_{m}\circ\mathrm{OR}_{m^2}$, where the two terms of the minimum meet; do not transfer it here. Upper bound here: $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(n)$. MinskyPapert69
\(\mathrm{s}(f)\) Sensitivity \(n = \sqrt 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 \(\Theta(n)\)
\(\lambda(f)\) Spectral sensitivity \(n\) $\lambda$ is exactly multiplicative: $\lambda = \lambda(\mathrm{AND}_n)\lambda(\mathrm{OR}_n) = \sqrt n\cdot\sqrt n$. ABKRT21
\(\mathrm{rdeg}(f)\) Rational degree \(n\) $\mathrm{ndeg}(f) = n\cdot\mathrm{ndeg}(\mathrm{OR}_n) = n$ and $\mathrm{ndeg}(\bar f)=\mathrm{ndeg}(\mathrm{NOR}_n)=n$. IJKKKSWW23
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n\)
\(\mathrm{C}^1(f)\) 1-certificate complexity \(n\)
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(n\)
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(n\)
\(\mathrm{FC}(f)\) Fractional certificate complexity \(n\)
\(\mathrm{EC}(f)\) Expectational certificate complexity \(n\) Between $\mathrm{fbs}=n$ and $\mathrm{C}=n$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N = n^2\)
\(\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(n) = \Theta(\sqrt N)\) $\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) = \Theta(n) = \Theta(\sqrt N)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(n) = \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(n) = \Theta(\sqrt N)$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n^2)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta(n^2)$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n^2)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{R}_{0}(f)$, with both ends $\Theta(n^2)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(n) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(n) = \Theta(\sqrt N)$ here.
\(\deg_2(f)\) Mod-2 degree \(N = n^2\) putative Over $\mathbb{F}_2$, $\mathrm{OR}_n = 1 + \prod_i(1+x_i)$ has top monomial $x_1\cdots x_n$ with coefficient $1$, and the outer AND multiplies the blocks' polynomials, so the full monomial survives. Characteristic $2$ buys nothing on a read-once formula.
\(\mathrm{s}^0(f)\) 0-sensitivity \(n\) putative Take one empty block and a single $1$ in each of the others: all $n$ bits of the empty block are sensitive, and nothing else is. Matches $\mathrm{s} = n$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(n\) putative Take exactly one $1$ per block: those $n$ bits are sensitive.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(n\) putative Certifying a $1$ needs a witness in each of the $n$ blocks; certifying a $0$ needs a whole empty block, $n$ bits. So every input costs exactly $n$: $\mathrm{C} = \mathrm{C}_{\min} = n$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(n),\ O(n^2)\) Not pinned at $\Theta(N)$: $\deg/2$ is a floor for $\mathrm{Q}_{\mathrm{E}}$, not for $\mathrm{Q}_0$, whose polynomial floor is $\mathrm{rdeg}/2 = \Theta(n)$ -- the same order as $\mathrm{Q} = \Theta(\sqrt N)$. The ceiling is $\mathrm{D} = n^2$ (equivalently $2\mathrm{R}_0$). So the zoo does not know whether zero error costs the full quadratic here.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n^2) = \Theta(N)\) Between $\mathrm{R} = \Theta(n^2)$ and $\mathrm{D}^{\mathrm{na}} = n^2$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(N = n^2\) putative A partition of the cube into monochromatic subcubes of codimension $\le k$ writes $f$ as the sum of the indicators of its $1$-subcubes, each a conjunction of $\le k$ literals and none of them cancelling, so $\deg(f) \le \mathrm{SP}(f)$. Here $\deg = \mathrm{D} = n^2$, so the chain $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$ collapses. Every read-once formula is pinned this way.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(N = n^2\) putative Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$ with $\deg = \mathrm{D} = n^2$; see the \(\mathrm{SP}(f)\) entry. Note how far this is from $\mathrm{C} = n$: the AND-OR tree is the standard $\mathrm{UC}$-vs-$\mathrm{C}$ gap.
\(\mathrm{rank}(f)\) Decision tree rank \(n = \sqrt N\) putative Upper: read the blocks left to right, and inside a block read bits until a $1$ appears. The block subtree has rank $1$, and grafting rank-$r$ subtrees onto the leaves of a rank-$1$ tree gives rank $\le r+1$, so $\mathrm{rank}_j = \mathrm{rank}_{j+1} + 1$ and the whole tree has rank $n$. Lower: $\mathrm{C}_{\min} = n$ here and $\mathrm{C}_{\min} \le \mathrm{rank}$ (a Delayer who always defers survives $\mathrm{C}_{\min}$ rounds). So $\mathrm{rank} = \mathrm{C}_{\min} = \mathrm{C} = n$ while $\mathrm{D} = n^2$.
\(\mathrm{DTsize}(f)\) Decision tree size \(\Theta(n^n) = 2^{\Theta(\sqrt N\log N)}\) putative Upper: the tree above has $S_j = n\,S_{j+1} + 1$ leaves for blocks $j..n$, i.e. $S_1 = (n^{n+1}-1)/(n-1) < \tfrac{n}{n-1}n^n$. Lower: the $n^n$ inputs with exactly one $1$ per block must reach distinct leaves, for if two of them differ in block $j$ then both of that block's $1$-positions are free in the common leaf-subcube, and zeroing the block stays inside it while flipping $f$ to $0$. So $n^n \le \mathrm{DTsize} \le \tfrac{n}{n-1}n^n$. Far above $2^{\mathrm{rank}} = 2^{n}$ and far below $2^{\mathrm{D}} = 2^{n^2}$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(n^2 2^{-n})\) putative Exactly $\mathrm{I}(f) = n^2\,2^{1-n}(1-2^{-n})^{n-1}$: bit $i$ of block $j$ is pivotal iff the rest of its block is $0$ and every other block is nonzero. The AND-OR tree is wildly unbalanced under the uniform measure -- $\Pr[f=1] = (1-2^{-n})^n \to 1$ -- so its total influence tends to $0$ even though $\mathrm{D} = N$. (Confirmed against the exact Fourier expansion for $n \le 4$.)
\(\hat{L}_1(f)\) Spectral norm \(\Theta(2^n) = \Theta(2^{\sqrt N})\) putative Exactly $\widehat{L}_1(f) = (2-2^{1-n})^{n+1} + |1 - 2(1-2^{-n})^{n}|$. In the $\pm1$ encoding the composed coefficients are $\hat f(T) = \pm 2^{1-n}(2^{1-n})^{|A|}(2-2^{1-n})^{\,n-|A|}$, where $A$ is the set of blocks $T$ touches, and all $T$ with the same $A$ share a sign, so the sum telescopes to a geometric one with no cancellation. Values $3.5,\ 9.71875,\ 23.719\ldots$ for $n = 2,3,4$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(N = n^2\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = n^2$, so even the cheaper side of the unambiguous cover costs the full $N$ -- against $\mathrm{C}_{\min} = n$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(n) = \Theta(\sqrt N)\) Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = n$ and $\mathrm{Q} = \Theta(n)$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(n^2) = \Theta(N)\) putative Pinned by the correct sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$ -- note $\mathrm{CG}$ is not capped by $\mathrm{D}$. Lower: $\mathrm{Adv}^2 = \Theta(n^2)$. Upper: $\mathrm{C}^0\mathrm{C}^1 = n\cdot n = n^2$. So the private-coin certificate game costs the full $N$ while the public-coin one costs only $\sqrt N$ -- the \(\mathrm{CG}(f)\) vs \(\mathrm{CG}^{\mathrm{pub}}(f)\) gap is quadratic here.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n) = \Theta(N^{1/4})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = n$ here.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n^2) = \Theta(N)\) For a Boolean-valued function pseudo-determinism is free -- the canonical answer is forced to be $f(x)$ -- so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$, and $\mathrm{R} = \Theta(n^2)$ here.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(n = \sqrt N\) Nondeterministic degree is multiplicative over the disjoint blocks of an AND: $\mathrm{ndeg}(\mathrm{AND}_n\circ g) = n\,\mathrm{ndeg}(g)$, and $\mathrm{ndeg}(\mathrm{OR}_n) = 1$ (the polynomial $\sum_i x_i$ is nonzero exactly on the $1$-inputs). This is the $\mathrm{ndeg}(f) = n$ half of the recorded \(\mathrm{rdeg}(f)\) value. IJKKKSWW23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(n) = \Theta(\sqrt N)\) De Wolf's exact characterisation $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ applied to the \(\mathrm{ndeg}(f)\) entry. Nondeterministic quantum queries are thus quadratically cheaper than $\mathrm{D} = N$ and match $\mathrm{Q}$.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(n^2 2^{-n})\) putative For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence agree, $\mathrm{I}^1(f) = \mathrm{I}(f)$; they can differ only for bounded real-valued $p$. So this is the \(\mathrm{I}(f)\) entry verbatim.
\(\mathrm{MaxInf}(f)\) Maximum influence \(\Theta(2^{-n})\) putative The function is transitive (permute the blocks, permute inside each block), so every coordinate has the same influence and $\max_i \mathrm{Inf}_i = \mathrm{I}(f)/N = 2^{1-n}(1-2^{-n})^{n-1}$ exactly, from the \(\mathrm{I}(f)\) entry.
\(\mathrm{Var}(f)\) Variance \(\Theta(n2^{-n}) = \Theta(\sqrt N\,2^{-\sqrt N})\) $4p(1-p)$ at $p = (1-2^{-n})^n = 1-\Theta(n2^{-n})$, as computed in the \(\mathrm{NS}_{\delta}(f)\) entry.
\(\mathrm{osss}(f)\) OSSS number \(\Theta(n) = \Theta(\sqrt N)\) putative $\Theta(n2^{-n})$ over $\Theta(2^{-n})$. Tight against $\mathrm{s} = n$, and quadratically short of $\mathrm{D} = N = n^2$ -- the two exponentially small Fourier quantities cancel and leave exactly the sensitivity.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(n) = \Theta(\sqrt N)\) putative $\mathrm{NS}_\delta = 2\Pr[f(x)=1,f(y)=0] = (2+o(1))n2^{-n}(1-(1-\delta)^n)$: the answer is $0$ only when some block is all-zero, and such a block stays all-zero exactly when none of its $n$ bits flips. Crossing $\mathrm{Var}/4$ needs $(1-\delta)^n \le \tfrac12$, so $\delta^{*} = \Theta(1/n)$. Tight against $4\mathrm{s} = 4n$.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(N = n^2\) putative The Fourier support is everything (see \(\mathrm{spar}(f)\)), so its $\mathbb{F}_2$-span is all of $\mathbb{F}_2^{N}$. In particular the bound $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}$ is vacuous here: parity queries have no structure to exploit on a read-once formula.
\(\mathrm{spar}(f)\) Fourier sparsity \(2^N = 2^{n^2}\) putative Full Fourier support: the closed form in the \(\hat{L}_1(f)\) note is nonzero for every $T$ (including $\hat f(\emptyset) = 1 - 2(1-2^{-n})^n$, which vanishes only at the degenerate $n=1$). Sparsity is therefore no better than the trivial bound even though $\mathrm{C} = \sqrt N$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(n\) Critical block sensitivity coincides with ordinary block sensitivity on a Boolean-valued problem [GoosPitassi14]: the only solution function is $f$ itself and every input is critical, so $\mathrm{cbs} = \mathrm{bs} = n$. GoosPitassi14
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n^2)\) Yao's minimax principle for worst-case cost: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3})$, and $\mathrm{R} = \Theta(n^2)$ here, so no distribution is harder than $\Theta(N)$ and some distribution is that hard. Yao77
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(n^2),\ O(n^2\log n)\) A noisy-query algorithm is in particular randomized, so $\mathrm{N}_p \ge \mathrm{R} = \Omega(n^2)$; repeating each query of an optimal randomized tree $O(\log \mathrm{R})$ times and taking majorities gives $\mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$ [FRPU94]. Whether the logarithm is needed here is open -- it is provably needed for \(\oplus_n\). FRPU94
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n^2)\) Always $\mathrm{noisyR} \le \mathrm{R}$, and the recorded implication $\mathrm{R}(f) = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ applies, since $\mathrm{R} = \Theta(n^2) = \Theta(N)$. So the composition theorem $\mathrm{R}(F\circ f^m) = \Omega(\mathrm{noisyR}(F)\,\mathrm{R}(f))$ loses nothing when this function is the outer one. CKMPSS23
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(n) = \Theta(\sqrt N)\)· Lower bound $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n)$. Upper bound: Grover search on bounded-error inputs costs $O(\sqrt m)$ calls with no logarithmic overhead [HoyerMoscadeWolf03], and noisy oracle access to a block can be turned into bounded-error access at constant amortised cost [BNRdW05]. Run robust search inside each $\mathrm{OR}_n$ block ($O(\sqrt n)$ noisy queries) and robust search again at the outer $\mathrm{AND}_n$ over the $n$ bounded-error block answers ($O(\sqrt n)$ calls): $O(n)$ in total. HoyerMoscadeWolf03 BNRdW05
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(N = n^2\) putative Parity queries buy nothing: $\deg_2 \le \mathrm{D}^{\oplus} \le \mathrm{D}$, and the recorded $\deg_2 = \mathrm{D} = N$ closes the sandwich.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\Theta(n2^{-n})\) putative For constant $\delta$ the noise sensitivity is within constants of the variance: in $\mathrm{NS}_\delta = \tfrac12\sum_{S\ne\emptyset}(1-(1-2\delta)^{|S|})\hat f(S)^2$ every factor lies in $[2\delta, 1]$, so $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$. Here $\Pr[f=1] = (1-2^{-n})^n = 1-\Theta(n2^{-n})$, hence $\mathrm{Var} = 4p(1-p) = \Theta(n2^{-n})$. Consistent with the recorded $\mathrm{I}(f) = \Theta(n^2 2^{-n})$ through $\mathrm{NS}_\delta \le \delta\,\mathrm{I}$. ODonnell14
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - \Theta(n2^{-n})\) putative From $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. The function is overwhelmingly biased towards $1$, so it is almost perfectly noise stable at every constant $\rho$ -- which is why the OSSS bound $\mathrm{D} \ge \mathrm{Var}/\mathrm{MaxInf}$ gives only $\Theta(n)$ here and not $\Theta(N)$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Omega(\sqrt n),\ O(n)\) Squeezed by $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg}$, whose ends are the recorded $\mathrm{sdeg} = \Omega(\sqrt n)$ and $\widetilde{\deg} = \Theta(n)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(n)\) Approximate rational degree is at most both $\mathrm{rdeg} = n$ and $\widetilde{\deg} = \Theta(n)$. No matching lower bound is available: $\mathrm{rdeg}_{1/3}$ is not known to be bounded below by any of $\mathrm{bs}$, $\lambda$ or $\mathrm{Q}$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(n)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], and \(\mathrm{rdeg}_{\varepsilon}(f)\) gives $\mathrm{rdeg}_{1/3} = O(n)$. Whether post-selection beats the ordinary quantum $\Theta(n)$ on this function is open, since no lower bound on $\mathrm{rdeg}_{1/3}$ is known here. MahadevdeWolf15
\(\deg_p(f)\) Mod-p degree \(N = n^2\) putative For every prime $p$. Over $\mathbb{F}_p$ one has $\mathrm{OR}_n(y) = 1-\prod_i(1-y_i)$, whose top monomial $\prod_i y_i$ carries coefficient $(-1)^{n+1}$, and $\mathrm{AND}_n$ is the plain product of its arguments; the blocks are disjoint, so the top monomial $\prod_{i,j}x_{ij}$ of the composition survives with coefficient $((-1)^{n+1})^n \ne 0$. Hence $\deg_p = \deg = N$ for all $p$, matching the recorded $\deg_2$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(n),\ O(n^2)\) Conical junta degree sits between approximate degree and randomized complexity, $\widetilde{\deg}_\varepsilon \le \mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon$, i.e. $\Omega(n)$ and $O(n^2)$ here. Closing the window would decide whether the non-negativity constraint costs anything on the canonical $\mathrm{Q}$-vs-$\mathrm{R}$ example.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Omega(n),\ O(n^2)\) The partition bound dominates block sensitivity, $\mathrm{prt}_{\varepsilon/4} \ge \varepsilon\,\mathrm{bs} + \log\varepsilon - 2 = \Omega(n)$, and is dominated by $2\mathrm{R} = O(n^2)$ [JainKlauck10, Thm 3.1]. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Omega(n),\ O(n^2)\)· The same sandwich as \(\mathrm{prt}_{\varepsilon}(f)\): the relaxed bound still dominates $\mathrm{bs}$ (the zoo's own $\mathrm{bs} \to \overline{\mathrm{prt}}$ record, which checks that the [JainKlauck10] argument never uses the completeness equality) and is at most $\mathrm{prt} \le 2\mathrm{R}$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Omega(n),\ O(n^2)\) The asymptotic composition rate obeys $\max\{\mathrm{Q},\ \Omega(\mathrm{LR})\} \le \mathrm{R}^{*} \le \mathrm{R}$ [BBGM22], and $\mathrm{Q} = \Theta(n)$, $\mathrm{R} = \Theta(n^2)$. Self-composing $\mathrm{AND}_n\circ\mathrm{OR}_n$ produces the balanced alternating $\mathrm{AND}/\mathrm{OR}$ tree of fan-in $n$, so $\mathrm{R}^{*}$ here is precisely the per-level randomized cost of deep read-once $\mathrm{AND}/\mathrm{OR}$ formulas: the same phenomenon that drops \(\bar{\wedge}\text{-tree}\) from exponent $1$ to $0.753$. BBGM22
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity \(n\) KLLPV26, Proposition 52: certifying a fixed input reduces to AND or OR on n bits (the family has N=n² inputs). KLLPV26
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) Exact quantum certification complexity \(\Theta(n)\) Certification costs at most its n-bit classical certificate; bounded degree certification n gives the quantum lower bound. KLLPV26
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) Zero-error quantum certification complexity \(\Theta(n)\) Theorem 5 and QEcert=Θ(n). KLLPV26
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n^2)\) Theorem 9.1; for LR use max-conflict ≤ O(LR) ≤ O(R). The conflict bound is the theorem’s bracket, not the stronger introduction-table upper bound. Meiburg26composition
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n^2)\) Theorem 9.1; for LR use max-conflict ≤ O(LR) ≤ O(R). The conflict bound is the theorem’s bracket, not the stronger introduction-table upper bound. Meiburg26composition
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n^2)\) Theorem 9.1; for LR use max-conflict ≤ O(LR) ≤ O(R). The conflict bound is the theorem’s bracket, not the stronger introduction-table upper bound. Meiburg26composition
\(\chi(f)\) Conflict complexity \(\Omega(n^2/\log^2 n),\ O(n^2/\log^{1/2}n)\) Theorem 9.1; for LR use max-conflict ≤ O(LR) ≤ O(R). The conflict bound is the theorem’s bracket, not the stronger introduction-table upper bound. Meiburg26composition

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. 326 in total, strongest first.

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

Notes

[Meiburg26composition, Theorem 9.1] gives $\mathrm{RS}=\bar\chi=\Theta(n^2)$ and $\Omega(n^2/\log^2 n)\le\chi\le O(n^2/\sqrt{\log n})$. Thus $\mathrm{RS}/\chi=\Omega(\sqrt{\log N})$, perfect conflict composition fails, and $\chi$ is not $O(\mathrm{C})$ (Corollaries 9.8, 9.9, 9.11).