Q The Query Complexity Zoo
\(f_{\mathrm{Rub}}\)

Rubinstein's function

The classical quadratic separation $\mathrm{bs} = \tfrac12\mathrm{s}^2$.

total composed arity: $N=n^2$ bits

Description

OR of $n$ copies of a gadget on $n$ bits that fires only on "two adjacent ones and nothing else".

Formal definition

Let $n$ be even. For $y \in \{0,1\}^n$ define $$g(y) = 1 \iff \exists k\in[n/2]:\ y_{2k-1}=y_{2k}=1 \text{ and } y_j = 0 \text{ for all } j \notin \{2k-1,2k\}.$$ Then $f_{\mathrm{Rub}}(y^1,\dots,y^n) = \bigvee_{j=1}^n g(y^j)$ on $N = n^2$ bits.

Measure values

MeasureValueNotes
\(\mathrm{s}(f)\) Sensitivity \(n = \sqrt N\) Achieved at an input where each block has a single $1$ in an odd position.
\(\mathrm{bs}(f)\) Block sensitivity \(n^2/2 = N/2\) At $0^N$: the $n/2$ adjacent pairs inside each of the $n$ blocks are disjoint sensitive blocks.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(N)\)
\(\mathrm{D}(f)\) Deterministic query complexity \(N\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(N)\) Between $\mathrm{bs}=N/2$ and $\mathrm{C}=\Theta(N)$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(N)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N\)
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{C}(f)$, with both ends $\Theta(N)$ here.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(N)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(N)$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(N)\) $\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) = \Theta(N)$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Omega(N),\ O(N^{3/2})\) Not pinned. The private-coin certificate game is not bounded by $\mathrm{D}$; the correct sandwich is $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1,\ O(\mathrm{EC}^2)\}$. Lower: $\mathrm{Adv}^2 \ge \mathrm{bs} = N/2$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(N)$ says the same. Upper: the two sides are lopsided, $\mathrm{C}^0\mathrm{C}^1 = (N/2)\cdot\sqrt N = \Theta(N^{3/2})$, which beats the $O(\mathrm{EC}^2) = O(N^2)$ route.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}}(f) = N$ here.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(N)\)· Sandwiched: $\mathrm{fbs}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
\(\mathrm{s}^0(f)\) 0-sensitivity \(n = \sqrt N\) putative At a $0$-input the pivotal bits are those that make some block fire. A block at a weight-$1$ input has exactly one such bit (complete the pair), and no block state has more, so $\mathrm{s}^0(f) = n\cdot\mathrm{s}^0(g) = n$. Brute force on the gadget gives $\mathrm{s}^0(g) = 1$ for $n = 4,6,8$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(n = \sqrt N\) putative A $1$-input has a firing block; all $n$ of its bits are sensitive (each flip destroys the pattern) and no bit outside it is. If two blocks fire the input is not sensitive at all, so $\mathrm{s}^1(f) = \mathrm{s}^1(g) = n$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(N/2 = n^2/2\) putative This is where $\mathrm{bs} = \tfrac12\mathrm{s}^2$ comes from: at $0^N$ each of the $n$ blocks offers its $n/2$ adjacent pairs as disjoint sensitive blocks, so $\mathrm{bs}^0(f) = n\cdot\mathrm{bs}^0(g) = n\cdot n/2$, against $\mathrm{s}^0 = n$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(n = \sqrt N\) putative Every sensitive block of a $1$-input must stop the firing block, so all of them meet its $n$ bits and at most $n$ are disjoint; the $n$ singletons work. So the quadratic gap is entirely one-sided: $\mathrm{bs}^0 = \tfrac12(\mathrm{bs}^1)^2$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(N/2 = n^2/2\) putative Certifying $0$ means certifying all $n$ blocks silent, and the worst block state is $0^n$, which needs one zero from each of its $n/2$ pairs. So $\mathrm{C}^0(f) = n\cdot\mathrm{C}^0(g) = n^2/2$ and $\mathrm{C} = \mathrm{C}^0 = N/2$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(n = \sqrt N\) putative Certifying $1$ means exhibiting one firing block, and a firing block must be pinned entirely (two ones and $n-2$ zeros): $\mathrm{C}^1(f) = \mathrm{C}^1(g) = n$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(n = \sqrt N\) putative The cheapest inputs are the $1$-inputs, at cost $\mathrm{C}^1 = n$; a $0$-input costs at least $2n$, since each of the $n$ blocks needs at least $\mathrm{C}_{\min}(g) = 2$ bits. So $\mathrm{C}_{\min} = \sqrt N$ against $\mathrm{C} = N/2$.
\(\deg(f)\) Exact degree \(N = n^2\) putative Degree is exactly multiplicative under block composition [Tal13], and $\deg(\mathrm{OR}_n) = n$. The gadget has full degree too: $g$ is the sum of $n/2$ point indicators, whose top monomials $y_1\cdots y_n$ all carry the same sign, so they add rather than cancel and $\deg(g) = n$. Hence $\deg = n\cdot n = N$, matching $\mathrm{D}$: this is a full-degree function with $\mathrm{s} = \sqrt N$, i.e. Huang's $\deg \le \mathrm{s}^2$ is tight here as well. Tal13
\(\deg_2(f)\) Mod-2 degree \(\Theta(N)\) putative Over $\mathbb{F}_2$, $\mathrm{OR}_n = 1 + \prod_j(1+g_j)$ and the blocks are disjoint, so the top monomial of $\prod_j g_j$ survives with coefficient $1$ and $\deg_2(f) = n\deg_2(g)$. For the gadget the coefficient of $y_1\cdots y_n$ is $n/2 \bmod 2$, so $\deg_2(g) = n$ when $n/2$ is odd and $n-1$ when $n/2$ is even; brute force gives $3, 6, 7$ at $n = 4,6,8$. Hence $\deg_2 = N$ or $N - \sqrt N$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(N\) putative A monochromatic subcube partition writes $f$ as a sum of indicators of subcubes of codimension $\le\mathrm{SP}$, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg = \mathrm{D} = N$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(N\) putative Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D} = N$; see \(\mathrm{SP}(f)\).
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(N)\) Between $\mathrm{fbs} = \Theta(N)$ and $\mathrm{C} = N/2$.
\(\lambda(f)\) Spectral sensitivity \(\sqrt N = n\) putative Pinned from both sides by the recorded chain $\sqrt{\deg} \le \lambda \le \mathrm{s}$: here $\deg = N$ and $\mathrm{s} = \sqrt N$ coincide at $\sqrt N$. Rubinstein's function is thus an extremal example for Huang's theorem in its spectral form. ABKRT21
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\sqrt N) = \Theta(n)\) putative Quantum query complexity composes exactly, $\mathrm{Q}(f\circ g) = \Theta(\mathrm{Q}(f)\mathrm{Q}(g))$, and $\mathrm{Q}(\mathrm{OR}_n) = \Theta(\sqrt n)$. For the gadget $\mathrm{Q}(g) = \Theta(\sqrt n)$: Grover over the $n/2$ pairs finds a fired pair in $O(\sqrt n)$ queries and a second Grover checks that no other bit is $1$; conversely restricting to the $n/2$ paired variables turns $g$ into $\mathrm{EXACT}_1$, which needs $\Omega(\sqrt n)$. So $\mathrm{Q} = \Theta(\sqrt n \cdot \sqrt n) = \Theta(\sqrt N)$, quadratically below $\mathrm{R} = \Theta(N)$ and matching the lower bound $\lambda = \sqrt N$. LMRSS11 Reichardt11 HLS07
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\sqrt N) = \Theta(n)\) putative Lower: $\mathrm{bs} \le 6\,\widetilde{\deg}^2$ with $\mathrm{bs} = N/2$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(\sqrt N)$. So the quadratic $\deg$-vs-$\widetilde{\deg}$ gap of [ABKRT21] is attained here as well. NS94
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(N)\) Between $\deg/2 = N/2$ and $\mathrm{D} = N$. Exact quantum query complexity is thus quadratically above $\mathrm{Q} = \Theta(\sqrt N)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(\sqrt N),\ O(N)\) Between $\mathrm{Q} = \Theta(\sqrt N)$ and $\mathrm{D} = N$. Not pinned by $\deg$: that floor bounds $\mathrm{Q}_{\mathrm{E}}$, while the $\mathrm{Q}_0$ floor is $\mathrm{rdeg}/2$, and $\mathrm{rdeg}$ is itself unpinned here.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(\sqrt N)\) putative Between $n$ and $2n$. Lower: $\mathrm{C}_{\min} \le \mathrm{rank}$ and $\mathrm{C}_{\min} = n$. Upper: the gadget has $\mathrm{rank}(g) = 2$ (query $y_1$; whichever way it goes, either the residual is a conjunction of literals or the same problem with one pair fewer -- verified exactly for $n \le 8$), and evaluating the blocks in turn grafts the remaining tree onto the $0$-leaves of a rank-$2$ tree, so $\mathrm{rank} \le 2n$.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Omega(\sqrt N)},\ 2^{O(\sqrt N\log N)}\) putative Lower: $\mathrm{DTsize} \ge 2^{\mathrm{rank}} \ge 2^{n}$. Upper: the block-by-block tree satisfies $S_j = a + b\,S_{j+1}$ where the optimal gadget tree has $a+b = \tfrac{n}{2}(\tfrac n2+2)$ leaves (exactly $8, 15, 24$ at $n = 4,6,8$), so $S_1 = n^{O(n)}$. Not pinned: the truth is somewhere between $2^{\Theta(\sqrt N)}$ and $2^{\Theta(\sqrt N\log N)}$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(N\) 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$, so both sides are pinned -- against $\mathrm{C}_{\min} = \sqrt N$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt N)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(N)$ here.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(N)\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(N)$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(N)\) putative Pinned. Upper: $\mathrm{RS} \le \mathrm{R}/(1-2\varepsilon) = O(N)$. Lower: $\mathrm{RS} = \Omega(\mathrm{bs}) = \Omega(N)$ -- at $0^N$, star out a uniformly random one of the $N/2$ disjoint adjacent pairs; every unstarred bit is $0$ as usual, so finding a $\ast$ is unstructured search over the $N/2$ pairs.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(N)\) putative Block sensitivity is supermultiplicative, so $\mathrm{R}(f^{\circ m}) \ge \mathrm{bs}(f)^m$ and $\mathrm{R}^{*} \ge \mathrm{bs} = N/2$; and $\mathrm{R}^{*} \le \mathrm{R} = \Theta(N)$ by submultiplicativity. Composition is perfect here for the trivial reason that $\mathrm{bs}$ and $\mathrm{R}$ already agree.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(\sqrt N) = \Theta(n)\) Sandwiched: $\lambda \le \mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, with $\lambda = \sqrt N$ and $\mathrm{Q} = \Theta(\sqrt N)$ here. Note $\mathrm{Adv}^2 = \Theta(N) = \Theta(\mathrm{bs})$: the basic adversary bound is exactly tight against block sensitivity on Rubinstein's function.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\sqrt N) = \Theta(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} = \Theta(\sqrt N)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\sqrt N) = \Theta(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} = \Theta(\sqrt N)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\sqrt N) = \Theta(n)\) Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants at $\Theta(\sqrt N)$ here.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(\sqrt N),\ O(N)\) Sandwiched: $\widetilde{\deg}_{\varepsilon} \le \mathrm{cjdeg}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\widetilde{\deg} = \Theta(\sqrt N)$ and $\mathrm{R} = \Theta(N)$ here. Non-negativity is exactly what could close this quadratic window, as it does on \(\bar{\wedge}\text{-tree}\).
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(N\) putative Sparsity is near-maximal (see \(\mathrm{spar}(f)\)) and in particular the gadget's singleton coefficients $\hat g(\{i\}) = 2^{-n}(n/2-2)$ are nonzero for $n \ge 6$, so every singleton of $[N]$ lies in the Fourier support and its $\mathbb{F}_2$-span is everything.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(n^3 2^{-n})\) putative For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; see \(\mathrm{I}(f)\).
\(\mathrm{MaxInf}(f)\) Maximum influence \(\Theta(n2^{-n})\) putative The automorphism group -- permute the blocks, permute the $n/2$ pairs inside a block, swap the two coordinates of a pair -- is transitive on all $N$ coordinates, so every coordinate carries influence $\mathrm{I}(f)/N = n\,2^{-n}(1-p)^{n-1}$ exactly, from the \(\mathrm{I}(f)\) entry.
\(\mathrm{Var}(f)\) Variance \(\Theta(n^2 2^{-n})\) $4p(1-p)$ at $p = 1-(1-(n/2)2^{-n})^n = \Theta(n^2 2^{-n})$, as computed in the \(\mathrm{NS}_{\delta}(f)\) entry.
\(\mathrm{osss}(f)\) OSSS number \(\Theta(n) = \Theta(\sqrt N)\) putative $\Theta(n^2 2^{-n})$ over $\Theta(n2^{-n})$. Tight against $\mathrm{s} = n$ and quadratically short of $\mathrm{D} = N$. Structurally identical to \(\mathrm{AND}_n \circ \mathrm{OR}_n\) and to \(f_{\mathrm{AS}}\): an OR of exponentially rare gadgets always lands on the sensitivity.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(n) = \Theta(\sqrt N)\) putative A firing gadget pins all $n$ of its bits, so it survives $\delta$-noise with probability $(1-\delta)^n$ and $\mathrm{NS}_\delta = (2+o(1))p(1-(1-\delta)^n)$ against $\mathrm{Var}/4 = (1+o(1))p$. Hence $\delta^{*} = \Theta(1/n)$, tight against $4\mathrm{s} = 4n$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(n^3 2^{-n})\) putative Exactly $\mathrm{I}(f) = n^3 2^{-n}(1-p)^{n-1}$ with $p = \tfrac n2 2^{-n} = \Pr[g = 1]$: the gadget has exactly $n^2$ sensitive edges out of $n2^{n}$, so $\mathrm{I}(g) = n^2 2^{-n}$, and a block's influence survives only if the other $n-1$ blocks stay silent. Under the uniform measure Rubinstein's function is almost constant, so its total influence is exponentially small even though $\mathrm{bs} = N/2$. (Checked against the full Fourier expansion at $n = 4$.)
\(\hat{L}_1(f)\) Spectral norm \(2^{\Theta(\sqrt N\log N)}\) putative Because the blocks are disjoint, $\widehat{L}_1(f) = |2(1-p)^n - 1| + 2\big[(1-p+\tfrac12 L')^n - (1-p)^n\big]$ exactly, where $L' = \sum_{S\ne\emptyset}|\hat g(S)|$ in the $\pm1$ encoding. For the gadget $\hat g(S)$ depends only on the number $t$ of pairs that $S$ splits, giving $L' = 2^{1-n/2}\sum_t \binom{n/2}{t}|n/2-2t| - 2p = \Theta(\sqrt n)$. Hence $\widehat{L}_1 = 2^{\Theta(n\log n)}$. Exact value $17.7578\ldots$ at $n = 4$, matching the full Fourier expansion.
\(\mathrm{spar}(f)\) Fourier sparsity \(\Theta(2^N)\) putative Near-maximal. Sparsity multiplies over the disjoint blocks, and the gadget misses only the $S$ that split exactly half of the $n/2$ pairs: $\hat g(S) = 2^{-n}\sum_j(-1)^{|S\cap\{2j-1,2j\}|}$ vanishes iff exactly $n/4$ pairs are split, so $\mathrm{spar}(g) = 2^n - \binom{n/2}{n/4}2^{n/2}$ for $n/2$ even and $2^n$ otherwise. Hence $\mathrm{spar}(f) = \mathrm{spar}(g)^n = (1-o(1))2^N$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(N/2 = n^2/2\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14]; the recorded $\mathrm{bs} = n^2/2$ is attained at the all-zeros input, whose $n^2/2$ sensitive blocks are the consecutive pairs. GoosPitassi14
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(N)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3}) = \Theta(N)$. Yao77
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(N),\ O(N\log N)\) $\mathrm{N}_p \ge \mathrm{R} = \Omega(N)$; amplifying each query $O(\log \mathrm{R})$ times gives the upper bound [FRPU94]. FRPU94
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(N)\) $\mathrm{noisyR} \le \mathrm{R}$, and $\mathrm{R} = \Theta(N)$ equals the arity, which forces $\mathrm{noisyR} = \Theta(\mathrm{R})$ by the recorded implication [CKMPSS23]. BenDavidBlais20composition CKMPSS23
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(\sqrt N),\ O(\sqrt N\log N)\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt N)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. BNRdW05
\(\chi(f)\) Conflict complexity \(\Theta(N)\) Pinned: $\chi = \Omega(\mathrm{bs}) = \Omega(N/2)$ [Li18] from below, and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(N)$ from above. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(N)\) Squeezed between $\chi = \Omega(\mathrm{bs}) = \Omega(N)$ and $\mathrm{LR} \le \mathrm{R} = O(N)$; also consistent with the recorded $\mathrm{RS} = \Theta(N) \le \bar\chi$ [GLSS19]. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(N)\) $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(N)$ and $\mathrm{LR} \le \mathrm{R} = O(N)$ [BBGM22]. So this gadget loses nothing as the inner function of a composition, despite the extreme $\mathrm{s}$-vs-$\mathrm{bs}$ gap. BBGM22
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(N)\) putative Parity queries do not help: $\deg_2 \le \mathrm{D}^{\oplus} \le \mathrm{D}$, and the recorded $\deg_2 = \Theta(N)$, $\mathrm{D} = N$ close the sandwich.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\Theta(n^2 2^{-n})\) putative For constant $\delta$, $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$, because each factor $1-(1-2\delta)^{|S|}$ with $|S| \ge 1$ lies in $[2\delta,1]$. A block is $1$ on exactly the $n/2$ inputs with one consecutive pair set, so $\Pr[g=1] = (n/2)2^{-n}$ and $\Pr[f=1] = 1-(1-(n/2)2^{-n})^n = \Theta(n^2 2^{-n})$; hence $\mathrm{Var} = 4p(1-p) = \Theta(n^2 2^{-n})$. Consistent with the recorded $\mathrm{I}(f) = \Theta(n^3 2^{-n})$ via $\mathrm{NS}_\delta \le \delta\,\mathrm{I}$. ODonnell14
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - \Theta(n^2 2^{-n})\) putative From $\mathrm{Stab}_\rho = 1-2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: the function is almost always $0$, hence almost perfectly noise stable.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\le n = \sqrt N\) $\mathrm{ndeg} \le \mathrm{C}^1 = n$: sum the indicators of the $n$-bit $1$-certificates (one per block pattern), all with positive coefficients, so the sum is nonzero exactly on $f^{-1}(1)$. Note this is $\sqrt{\deg}$ -- an extreme example of nondeterministic degree collapsing below the exact degree $N$. IJKKKSWW23
\(\mathrm{rdeg}(f)\) Rational degree \(\le N/2\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$ [IJKKKSWW23]; the first term is $\le n$ by the \(\mathrm{ndeg}(f)\) entry, and the second is $\le \mathrm{C}^0 = N/2$. The $0$-side dominates, so exact rational degree cannot be pushed below $\mathrm{C}^0$ by this argument. IJKKKSWW23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\le \lceil n/2\rceil\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil \le \lceil n/2\rceil$ [deWolf03], i.e. $O(\sqrt N)$ -- matching $\mathrm{Q} = \Theta(\sqrt N)$ up to constants, so nondeterminism buys nothing quantumly here. deWolf03
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(\sqrt N)\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(\sqrt N)$.
\(\mathrm{sdeg}(f)\) Sign degree \(O(\sqrt N)\) From $\mathrm{sdeg} \le \widetilde{\deg} = \Theta(\sqrt N)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(\sqrt N)\) At most $\widetilde{\deg} = \Theta(\sqrt N)$; the competing bound $\mathrm{rdeg} \le N/2$ is far weaker.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(\sqrt N)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and $\mathrm{rdeg}_{1/3} \le \widetilde{\deg} = O(\sqrt N)$; since $\mathrm{Q} = \Theta(\sqrt N)$, post-selection saves at most a constant factor unless the approximate rational degree collapses further. MahadevdeWolf15

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. 2 in total.

Separations it witnesses

Cited as a witness by

Notes

The best known upper bound in the other direction is still exponential: $\mathrm{bs}(f) \le \tfrac{e}{\sqrt{2\pi}} e^{\mathrm{s}(f)}\sqrt{\mathrm{s}(f)}$ [KenyonKutin04]. Whether $\mathrm{bs} = O(\mathrm{s}^2)$ -- the sensitivity-vs-block-sensitivity question -- is wide open and is not resolved by Huang's theorem.