Q The Query Complexity Zoo
\(\mathrm{ADDR}_k\)

ADDRESS / multiplexer

The standard gadget in lifting theorems and in "adaptivity is necessary" arguments.

total basic arity: $k + 2^k$ bits— also: MUX, index function, storage access function

Description

Input is $(a, y)$ with $a \in \{0,1\}^k$ an address and $y \in \{0,1\}^{2^k}$ a table; the output is $y_a$.

Formal definition

$\mathrm{ADDR}_k(a, y) = y_{\mathrm{bin}(a)}$ where $\mathrm{bin}(a)\in\{0,\dots,2^k-1\}$ is the integer encoded by $a$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(k+1\)
\(\deg(f)\) Exact degree \(k+1\)
\(\mathrm{s}(f)\) Sensitivity \(k+1\)
\(\mathrm{bs}(f)\) Block sensitivity \(k+1\)
\(\mathrm{C}(f)\) Certificate complexity \(k+1\)
\(\mathrm{C}^0(f)\) 0-certificate complexity \(k+1\)
\(\mathrm{C}^1(f)\) 1-certificate complexity \(k+1\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(k+1\) Between $\mathrm{bs}=k+1$ and $\mathrm{C}=k+1$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(k+1\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(k)\) At most $\mathrm{D}=k+1$, and at least $\mathrm{bs}/3 = \Omega(k)$. Nisan91
\(\hat{L}_1(f)\) Spectral norm \(2^k\) Write $\mathrm{ADDR}_k = \sum_a \mathbb{1}[\mathrm{addr}=a]\cdot y_a$: each term has spectral norm $1$ and the $2^k$ terms have disjoint Fourier supports, so the norms add.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Theta(k)\) Upper: $\mathrm{ndeg} \le \mathrm{C}^{1} = k+1$, and in fact $\sum_a \mathbb{1}[\mathrm{addr}=a]\,y_a$ is the function, of degree $k+1$. Lower: restrict the data table to $e_{a_0}$; the restriction is $\mathbb{1}[\mathrm{addr}=a_0]$, and a polynomial that is nonzero at exactly one point of $\{0,1\}^k$ is a scalar multiple of that point indicator, of degree $k$. So $\mathrm{ndeg} \in \{k, k+1\}$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(k)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2 \rceil$ [deWolf00], and $\mathrm{ndeg} = \Theta(k)$ above. Together with $\hat L_1 = 2^k$ this is the zoo's only family separating spectral norm from either nondeterministic measure -- and the gap is exponential, not polynomial. deWolf00
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(k + 2^k\) Every data bit is relevant, so a non-adaptive algorithm reads the entire table.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(2^k)\) A fixed distribution over $m$ data bits contains the addressed one with probability at most $m/2^k$; otherwise the algorithm is guessing an unbiased bit.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(2^k)\) Theorem 8: $\mathrm{noisyR}^{\mathrm{na}} = \Theta(\mathrm{R}^{\mathrm{na}})$ for partial Boolean functions. Against $\mathrm{noisyR} \le \mathrm{R} = \Theta(k)$, this is an exponential separation between the adaptive and non-adaptive noisy models -- adaptivity is what lets the algorithm aim its bias budget at the addressed cell, exactly as in the noiseless case. BenDavidBlais20composition
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(k+1)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(k+1\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(k+1)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = k+1$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(k+1)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = k+1$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(k+1)\) 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(k+1)\) 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
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(k+1)\) Sandwiched: $\mathrm{s}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(k+1\) Sandwiched: $\mathrm{C}^1(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\chi(f)\) Conflict complexity \(\Theta(k+1)\) Sandwiched: $\mathrm{s}(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(k+1)\) Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(k+1)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(k+1)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(k^2)\) putative Both ends of the [CGLMSG23] sandwich land on $k^2$: $\mathrm{Adv}^2 = \Theta(k^2)$ from below and $\mathrm{C}^0\mathrm{C}^1 = (k+1)^2$ from above. So the address function too has $\mathrm{CG}$ above its own decision-tree complexity $k+1$ -- quadratically so. CGLMSG23
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(k+1)\) Sandwiched: $\deg(f)/2 \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$ -- the same halving as on \(\mathrm{Tribes}_{w,s}\) -- with $\deg(f) = k+1$ and $\mathrm{D}(f) = k+1$ here, so both ends are $\Theta(k)$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(k+1)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(k+1)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k+1$ 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{s}^0(f)\) 0-sensitivity \(k+1\) putative Take $y \equiv 0$ except $y_a = 0$ with all $2^k$ table entries chosen so that every address-neighbour of $a$ carries a $1$: then all $k$ address bits and $y_a$ itself are sensitive. Complementing the table swaps the two sides, so $\mathrm{s}^0 = \mathrm{s}^1$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(k+1\) putative By the complement symmetry $\mathrm{ADDR}_k(a,\bar y) = 1 - \mathrm{ADDR}_k(a,y)$, the two sides are equal; see $\mathrm{s}^0$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(k+1\) Squeezed between $\mathrm{s}^0 = k+1$ and $\mathrm{bs} = k+1$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(k+1\) Squeezed between $\mathrm{s}^1 = k+1$ and $\mathrm{bs} = k+1$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(k+1\) putative A certificate that fixes $j$ of the address bits leaves $2^{k-j}$ live addresses and must therefore pin all $2^{k-j}$ of the corresponding table entries, for a total of $j + 2^{k-j} \ge k+1$ coordinates, with equality only at $j=k$ (and $j=k-1$). So every input has $\mathrm{C}(x) = k+1$: $\mathrm{C} = \mathrm{C}_{\min} = k+1$ and $\mathrm{ADDR}$ is perfectly balanced in certificate size.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(k+1\) putative The family $\{a \text{ fixed},\, y_a = b\}$ over all $2^k$ addresses is unambiguous -- each input matches exactly one member per output value -- and has width $k+1 = \mathrm{C}$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(k+1\) Between $\mathrm{C}_{\min} = k+1$ and $\mathrm{UC} = k+1$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(k+1\) putative The natural tree (read the address, then the addressed entry) partitions the cube into codimension-$(k+1)$ monochromatic subcubes, and no monochromatic subcube can have codimension below $\mathrm{C}_{\min} = k+1$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(k+1\) Between $\mathrm{fbs} = k+1$ and $\mathrm{C} = k+1$.
\(\mathrm{rank}(f)\) Decision tree rank \(k+1\) putative Upper: $\mathrm{rank} \le \mathrm{D} = k+1$. Lower: in the Prover--Delayer game the Delayer defers on every query, so the game lasts at least $\mathrm{C}_{\min}$ rounds; in general $\mathrm{C}_{\min}(f) \le \mathrm{rank}(f)$, and here $\mathrm{C}_{\min} = k+1$. So $\mathrm{ADDR}$ has full rank: none of its depth is caterpillar.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{k+1}\) putative Each leaf-subcube is monochromatic, hence of codimension $\ge \mathrm{C}_{\min} = k+1$, hence of measure $\le 2^{-(k+1)}$; the leaves partition the cube, so there are at least $2^{k+1}$ of them. The natural tree achieves it: $2^k$ address paths, each ending in one table query.
\(\deg_2(f)\) Mod-2 degree \(k+1\) putative Over $\mathbb{F}_2$, $\mathrm{ADDR}_k = \sum_a \big(\prod_{i:\,a_i=1} z_i \prod_{i:\,a_i=0} (1+z_i)\big)\, y_a$ with $z$ the address. Each summand has the top monomial $z_1\cdots z_k\, y_a$, and these carry distinct table variables, so nothing cancels: $\deg_2 = k+1$.
\(\mathrm{sdeg}(f)\) Sign degree \(\Theta(k)\) putative Restricting the table to $y_b = \mathrm{parity}(b)$ turns $\mathrm{ADDR}_k$ into $\mathrm{PARITY}_k$, and sign degree cannot increase under restriction, so $\mathrm{sdeg} \ge \mathrm{sdeg}(\mathrm{PARITY}_k) = k$; also $\mathrm{sdeg} \le \deg = k+1$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(k)\) Squeezed between $\mathrm{sdeg} = \Omega(k)$ and $\deg = k+1$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(k)\) Squeezed between $\widetilde{\deg}/2 = \Omega(k)$ and $\mathrm{D} = k+1$. Quantum buys nothing on the multiplexer.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(k)\) Between $\mathrm{Q} = \Omega(k)$ and $\mathrm{D} = k+1$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(k)\) Between $\sqrt{\mathrm{bs}^0\,\mathrm{bs}^1} = k+1$ and $\mathrm{Q} = O(k)$.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(k)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(k)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(k)\) Also $\Theta(\mathrm{Q})$ for every $f$, and $\mathrm{Q} = \Theta(k)$ here.
\(\mathrm{I}(f)\) Total influence (L2 influence) \((k+2)/2\) putative Flipping an address bit moves the pointer to a uniformly unrelated table entry, flipping the output with probability $1/2$: total $k/2$. Flipping table entry $y_b$ matters exactly when $\mathrm{bin}(a) = b$, probability $2^{-k}$, and there are $2^k$ of them: total $1$. So $\mathrm{Inf} = k/2 + 1$.
\(\mathrm{MaxInf}(f)\) Maximum influence \(1/2\) putative Attained by any address bit (for $k \ge 1$); each table bit has influence only $2^{-k}$.
\(\mathrm{Var}(f)\) Variance \(1\) Balanced: the addressed data bit is uniform.
\(\mathrm{osss}(f)\) OSSS number \(2\) putative $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = 1/2$ (the addressed bit is pivotal with probability $1/2$). Against $\mathrm{D} = k+1$ this is only tight for $k = O(1)$.
\(\mathrm{nsr}(f)\) Noise robustness \(k/\ln 2\,(1+o(1)) = \Theta(\log N)\) putative $\tfrac12(1-(1-2\delta)(1-\delta)^k) = \tfrac14$ at $(1-\delta)^k \to \tfrac12$, so $\delta^{*} = (\ln 2)/k\,(1+o(1))$: the answer survives exactly as long as none of the $k$ address bits flips. Tight against $\mathrm{D} = k+1$ -- one of the few functions in the zoo where the critical noise rate sees the whole decision tree.
\(\mathrm{spar}(f)\) Fourier sparsity \(4^k\) putative In the $\pm 1$ basis each of the $2^k$ terms $\mathbb{1}[\mathrm{addr}=a]\,y_a$ expands into $2^k$ monomials of coefficient $\pm 2^{-k}$, and the $y_a$ factor keeps the supports of different $a$ disjoint. Consistent with the recorded $\mathrm{L}_1 = 4^k \cdot 2^{-k} = 2^k$.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(k + 2^k\) putative The Fourier support contains every singleton $\{y_a\}$ and every subset of the address bits, so it spans all $n$ coordinates over $\mathbb{F}_2$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(k)\) From $\mathrm{R}(f) = \Theta(k) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. CKMPSS23
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(k)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BenDavidKothari18
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(k)\) $\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(k)$ here.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt k)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(k)$ here. Aaronson08
\(\lambda(f)\) Spectral sensitivity \(\Theta(k)\) putative Upper: $\lambda(f) \le \mathrm{s}(f) = k+1$. Lower: the spectral norm of a graph is at least its average degree, and the average degree of the sensitivity graph is exactly $\mathrm{I}(f) = (k+2)/2$.
\(\mathrm{I}^{1}(f)\) Total L1 influence \((k+2)/2\) Boolean-valued, so equal to $\mathrm{I}(f)$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(k)\) Squeezed: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(k)$ here.
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(k)\) Squeezed: $\mathrm{ndeg}(f) \le \mathrm{rdeg}(f) \le \mathrm{C}(f)$, with $\mathrm{ndeg}(f) = \Theta(k)$ recorded above and $\mathrm{C}(f) = k+1$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(k)\) putative Squeezed between $\mathrm{odeg}(\mathrm{PARITY}_k) = k$ -- restrict the table to $y_b = \mathrm{parity}(b)$, as on the \(\mathrm{sdeg}(f)\) line, and note that one-sided approximation survives restriction -- and $\widetilde{\deg}(f) = O(k)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\Theta(k)\) putative Upper: $\mathrm{rdeg}_{\varepsilon} \le \mathrm{rdeg} = O(k)$. Lower: the same restriction to $\mathrm{PARITY}_k$, whose approximate rational degree is $\Theta(k)$. So postselection does not help the multiplexer at all. MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(k)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f)) = \Theta(k)$. MahadevdeWolf15
\(\deg_p(f)\) Mod-p degree \(k+1\) putative For every prime $p$: the expansion $\sum_a \big(\prod_{i:a_i=1} z_i \prod_{i:a_i=0}(1-z_i)\big) y_a$ used for $\deg_2$ has top monomials $z_1\cdots z_k\,y_a$ with coefficient $\pm1$, nonzero in every characteristic, and they cannot cancel because they carry distinct table variables.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(k)\) putative Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = k+1$. Lower: a depth-$d$ parity decision tree has at most $2^d$ leaves, each an affine subspace of codimension $\le d$ whose indicator has Fourier support of size $2^d$, so $\mathrm{spar}(f) \le 4^{d}$; with $\mathrm{spar} = 4^k$ this forces $d \ge k$. Parity queries save at most one query on the multiplexer.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(k)\) putative Take the uniform distribution. A tree of depth $m$ leaves at least $k-m$ address bits unread, so the addressed entry is uniform over $\ge 2^{k-m}$ candidates of which at most $m$ have been read; for $m \le k/2$ the algorithm identifies it with probability $\le m2^{-k/2}$ and is otherwise flipping a fair coin. Hence $\mathrm{D}^{\mathrm{prod}} = \Omega(k)$, matching $\mathrm{D} = k+1$. (The exact optimum is $k$, not $k+1$: read $k-1$ address bits and one of the two surviving entries, and guess when the address misses -- error $1/4$.)
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(k\log k)\)· putative Upper: $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log\mathrm{R}(f))$ by repeating each query $O(\log k)$ times. Lower: $\mathrm{N}_p(f) = \Omega(\mathrm{I}(f)\log\mathrm{I}(f))$ [GLX26noisy] with $\mathrm{I}(f) = (k+2)/2$. The two meet, so the multiplexer joins \(\oplus_n\) and \(\mathrm{Nav}_k\) as a family where the repetition log factor is provably necessary -- unsurprisingly, since a single corrupted address bit sends the walk to an unrelated table entry. GLX26noisy FRPU94
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(\rho\big(\tfrac{1+\rho}{2}\big)^{k}\) putative Exactly. In the $\pm1$ basis $g = 2^{-k}\sum_a\sum_{S \subseteq [k]} \pm\,\chi_S\,Y_a$, so every one of the $4^k$ Fourier coefficients is $\pm2^{-k}$ and the set $S \cup \{y_a\}$ has size $|S|+1$; summing, $\mathrm{Stab}_\rho = 2^{-2k}\,2^k\rho\sum_{S}\rho^{|S|} = 2^{-k}\rho(1+\rho)^k$. Identical in form to \(\mathrm{Nav}_k\) with one more level, as it should be.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\tfrac12\big(1-(1-2\delta)(1-\delta)^{k}\big)\) putative The \(\mathrm{Stab}_{\rho}(f)\) line at $\rho = 1-2\delta$, through $\mathrm{NS}_\delta = \tfrac12(1-\mathrm{Stab}_{1-2\delta})$. Noise on the address, not on the table, is what destroys the answer: the table contributes only the leading factor $1-2\delta$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(k),\ O(k\log k)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(k)$. Upper: read the address and the entry classically, repeating each query $O(\log k)$ times. The universal $O(\mathrm{arity})$ bound of [BNRdW05] is useless here, the arity being $k+2^k$. BNRdW05
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(k)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(k)$; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform distribution attains it. Yao77
\(\mathrm{cbs}(S)\) Critical block sensitivity \(k+1\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $k+1$ here by the \(\mathrm{bs}(f)\) line. GoosPitassi14
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(k)\) 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(k)$. CDM23
\(\mathrm{QS}_{\mathrm{weak}}(f)\) Weak quantum sabotage complexity \(\Theta(k)\) CMP24 Theorem 5.3 and Appendix B: all four sabotage variants equal Θ(k). The paper’s parameter n is the address length k used here. CMP24
\(\mathrm{QS}_{\mathrm{str}}(f)\) Strong quantum sabotage complexity \(\Theta(k)\) CMP24 Theorem 5.3 and Appendix B: all four sabotage variants equal Θ(k). The paper’s parameter n is the address length k used here. CMP24
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) Weak quantum sabotage index complexity \(\Theta(k)\) CMP24 Theorem 5.3 and Appendix B: all four sabotage variants equal Θ(k). The paper’s parameter n is the address length k used here. CMP24
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) Strong quantum sabotage index complexity \(\Theta(k)\) CMP24 Theorem 5.3 and Appendix B: all four sabotage variants equal Θ(k). The paper’s parameter n is the address length k used here. CMP24
\(\lambda^{\mathrm{cert}}(f)\) Spectral sensitivity certification \(\sqrt{k+1}\) Theorem 42: λcert=√s, and s=k+1. KLLPV26

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

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