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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{noisyR}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{Var}(f_n) = O(1)\)from \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(2^k)\) against \(\mathrm{Var}(f) = 1\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = 2^{\Omega(\mathrm{D}(f_n))}\)from \(\mathrm{D}^{\mathrm{na}}(f) = k + 2^k\) against \(\mathrm{D}(f) = k+1\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) = 2^{\Omega(\mathrm{s}(f_n))}\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(2^k)\) against \(\mathrm{s}(f) = k+1\)
-
\(\hat{L}_1(f_n) = 2^{\Omega(\mathrm{bs}(f_n))}\)from \(\hat{L}_1(f) = 2^k\) against \(\mathrm{bs}(f) = k+1\)
-
\(\dim_{\mathbb{F}_2}(f_n) = 2^{\Omega(\mathrm{D}^{\oplus}(f_n))}\)from \(\dim_{\mathbb{F}_2}(f) = k + 2^k\) against \(\mathrm{D}^{\oplus}(f) = \Theta(k)\)
-
\(\mathrm{QS}_{\mathrm{weak}}(f_n) = \Omega\big(\mathrm{QC}(f_n)^{2}\big)\)from \(\mathrm{QS}_{\mathrm{weak}}(f) = \Theta(k)\) against \(\mathrm{QC}(f) = \Theta(\sqrt k)\)
-
\(\mathrm{PostQ}_{\varepsilon}(f_n) = \Omega\big(\mathrm{RC}(f_n)\big)\)from \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(k)\) against \(\mathrm{RC}(f) = \Theta(k+1)\)
-
\(\mathrm{sdeg}(f_n) = \Omega\big(\deg_p(f_n)\big)\)from \(\mathrm{sdeg}(f) = \Theta(k)\) against \(\deg_p(f) = k+1\)
-
\(\mathrm{QS}_{\mathrm{str}}(f_n) = \Omega\big(\mathrm{C}(f_n)\big)\)from \(\mathrm{QS}_{\mathrm{str}}(f) = \Theta(k)\) against \(\mathrm{C}(f) = k+1\)
-
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f_n) = \Omega\big(\mathrm{UC}(f_n)\big)\)from \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f) = \Theta(k)\) against \(\mathrm{UC}(f) = k+1\)
-
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f_n) = \Omega\big(\mathrm{UC}_{\min}(f_n)\big)\)from \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f) = \Theta(k)\) against \(\mathrm{UC}_{\min}(f) = k+1\)
-
\(\mathrm{noisyR}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(2^k)\) against \(\mathrm{MaxInf}(f) = 1/2\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{Var}(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^k\) against \(\mathrm{Var}(f) = 1\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = 2^{\Omega(\mathrm{s}(f_n))}\)from \(\mathrm{D}^{\mathrm{na}}(f) = k + 2^k\) against \(\mathrm{s}(f) = k+1\)
… and 398 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Exponential, on a total function: $\mathrm{D}^{\mathrm{na}} = k + 2^k$ while $\mathrm{D} = k+1$. Adaptivity is what lets you skip the table. Compare \(\mathrm{Nav}_k\), where the same gap arises with no promise and no gadget.
-
Exponential: $\mathrm{R}^{\mathrm{na}} = \Theta(2^k)$ against $\mathrm{R} = \Theta(k)$ -- randomness does not substitute for adaptivity here, since a non-adaptive sampler misses the addressed entry.
Cited as a witness by
-
\(\mathrm{noisyR}(\mathrm{ADDR}_k) = O(k) \text{ while } \mathrm{noisyR}^{\mathrm{na}}(\mathrm{ADDR}_k) = \Theta(2^k)\)
-
\(\hat L_1(\mathrm{ADDR}_k) = 2^k = \tfrac12\,\mathrm{DTsize}(\mathrm{ADDR}_k)\)
-
\(\hat L_1(\mathrm{ADDR}_k) = 2^k = 2^{\mathrm{D}(\mathrm{ADDR}_k)-1}\)
-
\(\mathrm{D}^{\mathrm{na}}(\mathrm{ADDR}_k) = k + 2^k,\quad \mathrm{D}(\mathrm{ADDR}_k) = k+1\)
-
\(\mathrm{R}^{\mathrm{na}}(\mathrm{ADDR}_k) = \Theta(2^k),\quad \mathrm{R}(\mathrm{ADDR}_k) = \Theta(k)\)
-
\(\mathrm{QS}_{\mathrm{weak}}(\mathrm{IND}_n)=\Theta(\mathrm{fbs}(\mathrm{IND}_n))\)
-
\(\mathrm{QS}_{\mathrm{str}}(\mathrm{IND}_n)=\Theta(\mathrm{fbs}(\mathrm{IND}_n))\)
-
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(\mathrm{IND}_n)=\Theta(\mathrm{fbs}(\mathrm{IND}_n))\)
-
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(\mathrm{IND}_n)=\Theta(\mathrm{fbs}(\mathrm{IND}_n))\)