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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f) = \Theta(n)\) against \(\mathrm{Stab}_{\rho}(f) = 1 - \Theta(n2^{-n})\)
-
\(\mathrm{D}(f_n) = \Omega\big(\mathrm{QC}(f_n)^{4}\big)\)from \(\mathrm{D}(f) = N = n^2\) against \(\mathrm{QC}(f) = \Theta(\sqrt n) = \Theta(N^{1/4})\)
-
\(\mathrm{D}^{\oplus}(f_n) = \Omega\big(\mathrm{s}(f_n)^{2}\big)\)from \(\mathrm{D}^{\oplus}(f) = N = n^2\) against \(\mathrm{s}(f) = n = \sqrt N\)
-
\(\mathrm{UC}(f_n) = \Omega\big(\mathrm{C}(f_n)^{2}\big)\)from \(\mathrm{UC}(f) = N = n^2\) against \(\mathrm{C}(f) = n\)
-
\(\mathrm{UC}_{\min}(f_n) = \Omega\big(\mathrm{bs}(f_n)^{2}\big)\)from \(\mathrm{UC}_{\min}(f) = N = n^2\) against \(\mathrm{bs}(f) = n\)
-
\(\mathrm{SP}(f_n) = \Omega\big(\mathrm{EC}(f_n)^{2}\big)\)from \(\mathrm{SP}(f) = N = n^2\) against \(\mathrm{EC}(f) = n\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = \Omega\big(\mathrm{fbs}(f_n)^{2}\big)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n^2)\) against \(\mathrm{fbs}(f) = n\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = \Omega\big(\mathrm{Q}_{0}^{\mathrm{cert}}(f_n)^{2}\big)\)from \(\mathrm{D}^{\mathrm{na}}(f) = N = n^2\) against \(\mathrm{Q}_{0}^{\mathrm{cert}}(f) = \Theta(n)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) = \Omega\big(\mathrm{RC}(f_n)^{2}\big)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(n^2)\) against \(\mathrm{RC}(f) = \Theta(n)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{FC}(f_n)^{2}\big)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(n^2)\) against \(\mathrm{FC}(f) = n\)
-
\(\mathrm{R}_{0}(f_n) = \Omega\big(\mathrm{cbs}(S)(f_n)^{2}\big)\)from \(\mathrm{R}_{0}(f) = \Theta(n^2)\) against \(\mathrm{cbs}(S) = n\)
-
\(\mathrm{R}^{1}(f_n) = \Omega\big(\mathrm{CA}(f_n)^{2}\big)\)from \(\mathrm{R}^{1}(f) = \Theta(n^2)\) against \(\mathrm{CA}(f) = \Theta(n)\)
-
\(\mathrm{RS}(f_n) = \Omega\big(\mathrm{CG}^{\mathrm{pub}}(f_n)^{2}\big)\)from \(\mathrm{RS}(f) = \Theta(n^2)\) against \(\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(n)\)
-
\(\chi(f_n) = \Omega\big(\mathrm{CG}^{*}(f_n)^{2}\big)\)from \(\chi(f) = \Omega(n^2/\log^2 n),\ O(n^2/\log^{1/2}n)\) against \(\mathrm{CG}^{*}(f) = \Theta(n)\)
… and 312 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Quadratic: $\mathrm{Q}_0 = \Theta(N)$ (forced by $\deg = N$) against $\mathrm{Q} = \Theta(\sqrt N)$ (robust quantum search). Zero error is exactly as expensive as no quantum at all here.
-
$\mathrm{D}=\mathrm{C}^2$; matches the upper bound $\mathrm{D}\le \mathrm{C}^0\mathrm{C}^1 \le \mathrm{C}^2$.
-
$\mathrm{D} = \mathrm{bs}^2$ (upper bound is $\mathrm{bs}^3$).
-
$\mathrm{D} = \mathrm{RC}^2$ (upper bound is $\mathrm{RC}^3$).
-
$\deg = \mathrm{s}^2$; matches Huang's $\deg \le \mathrm{s}^2$ exactly.
-
$\deg = \mathrm{C}^2$.
-
$\mathrm{Q}_E = \mathrm{C}^2$.
Cited as a witness by
-
\(\mathrm{D}(f_n) = \mathrm{C}(f_n)^2\)
-
\(\mathrm{D}(f_n) = \mathrm{bs}(f_n)^2\)
-
\(\deg(f_n) = \mathrm{s}(f_n)^2\)
-
\(\chi(F_n)=\Omega(\mathrm{C}(F_n)^2/\log^2\mathrm{C}(F_n))\)
-
\(\chi(\mathrm{AND}_n\circ\mathrm{OR}_n)=O\!\left(\frac{\chi(\mathrm{AND}_n)\chi(\mathrm{OR}_n)}{\sqrt{\log n}}\right)\)
-
\(\deg(\mathrm{ANDOR}_{m^2})=\Theta((\overline{\deg}^{\mathrm{cert}}(\mathrm{ANDOR}_{m^2}))^2)\)
-
\(\mathrm{RS}(F_n)/\chi(F_n)=\Omega(\sqrt{\log N}),\qquad N=n^2\)
-
\(\bar\chi(F_n)/\chi(F_n)=\Omega(\sqrt{\log N}),\qquad N=n^2\)
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).