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

Ambainis-Sun function

Improves Rubinstein's constant to $\mathrm{bs} = \tfrac23 \mathrm{s}^2 - \tfrac13 \mathrm{s}$.

total composed arity: $N=(4k+2)(3k+2)$ bits

Description

An OR of $3k+2$ copies of a gadget $g$ on $n = 4k+2$ bits, exactly as in \(f_{\mathrm{Rub}}\) but with a cleverer gadget: $g$ fires on $2k+1$ cyclic patterns, each of which pins $3k+2$ of the $n$ coordinates (rather than all of them), so the gadget keeps $\mathrm{s}^0(g)=1$ and $\mathrm{bs}^0(g)=n/2$ while raising $\mathrm{s}^1(g)$ from $n$ only to $3k+2 = \tfrac34 n + \tfrac12$. Since the OR level multiplies $\mathrm{s}^0$ and $\mathrm{bs}^0$ by the number of blocks but leaves $\mathrm{s}^1$ alone, taking $3k+2$ blocks balances the two sides and buys the factor $4/3$ over Rubinstein.

Formal definition

$$f(x^1,\dots,x^{3k+2}) = \bigvee_{i=1}^{3k+2} g(x^i), \qquad g(y_1,\dots,y_{4k+2}) = 1 \iff \exists j\in[2k+1]:\ y \sim P_j,$$ where the pattern $P_j$ demands $y_{2j-1}=y_{2j}=1$ and $y_{2j+2i}=y_{2j-2i-1}=y_{2j-2i}=0$ for all $i\in[k]$, indices taken modulo $n=4k+2$. Any two patterns are at Hamming distance $\ge 3$, which is what forces $\mathrm{s}^0(g)=1$.

Measure values

MeasureValueNotes
\(\mathrm{bs}(f)\) Block sensitivity \(6k^2+7k+2\) Attained at the all-zero input: $\mathrm{bs}^0(f) = (3k+2)\cdot\mathrm{bs}^0(g) = (3k+2)(2k+1)$, since flipping the $j$-th pattern's two $1$-bits inside any block turns $f$ on, and blocks from different copies are disjoint. With $\mathrm{s} = 3k+2$ this is exactly $\tfrac23\mathrm{s}^2 - \tfrac13\mathrm{s}$, the current record constant for the quadratic separation. AmbainisSun11
\(\mathrm{s}(f)\) Sensitivity \(3k+2\) Both sides agree: $\mathrm{s}^0(f) = (3k+2)\mathrm{s}^0(g) = 3k+2$ and $\mathrm{s}^1(f) = \mathrm{s}^1(g) = 3k+2$. Balancing them is exactly how the number of blocks was chosen. AmbainisSun11
\(\mathrm{s}^0(f)\) 0-sensitivity \(3k+2\) Sensitivity of an OR of blocks is $n_{\mathrm{blocks}}\cdot\mathrm{s}^0$ of the gadget, and the Ambainis--Sun gadget has $\mathrm{s}^0(g) = 1$: two single-bit flips of a $0$-input landing in different patterns would put those patterns at Hamming distance $\le 2$, contradicting the distance-$3$ property. AmbainisSun11
\(\mathrm{s}^1(f)\) 1-sensitivity \(3k+2\) $\mathrm{s}^1(f) = \mathrm{s}^1(g)$ for an OR of blocks, and a $1$-input of $g$ satisfies exactly one pattern, whose $3k+2$ pinned bits are the only candidates for sensitivity -- all of them sensitive at $y = 110\cdots0$. AmbainisSun11
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(6k^2+7k+2\) The value of \(\mathrm{bs}(f)\); $\mathrm{bs}^0(g) = 2k+1$ because disjoint sensitive blocks must switch on distinct patterns. AmbainisSun11
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(3k+2\) putative Every sensitive block of a $1$-input must destroy the pattern that is firing, so it meets that pattern's $3k+2$ pinned bits; at most $3k+2$ such blocks are disjoint, and the singletons work. So the separation is one-sided, as in \(f_{\mathrm{Rub}}\).
\(\mathrm{C}^0(f)\) 0-certificate complexity \(6k^2+7k+2\) putative Certifying $f=0$ means certifying all $3k+2$ blocks silent, and $\mathrm{C}^0(g) = 2k+1$ exactly: from any $0$-input of $g$, naming one coordinate that already violates each of the $2k+1$ patterns is a certificate, and $\mathrm{C}^0(g) \ge \mathrm{bs}^0(g) = 2k+1$. So $\mathrm{C}^0(f) = (3k+2)(2k+1) = \mathrm{bs}^0(f)$: block sensitivity and certificate complexity coincide. (Brute force confirms $\mathrm{C}^0(g) = 3, 5$ at $k = 1,2$.)
\(\mathrm{C}^1(f)\) 1-certificate complexity \(3k+2\) putative A firing pattern is a $1$-certificate of size $3k+2$, and $\mathrm{C}^1 \ge \mathrm{s}^1 = 3k+2$.
\(\mathrm{C}(f)\) Certificate complexity \(6k^2+7k+2\) putative $\max\{\mathrm{C}^0,\mathrm{C}^1\}$; the $0$-side dominates quadratically.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(3k+2\) putative The $1$-inputs are the cheap ones: $\mathrm{C}_{\min} = \mathrm{C}^1 = 3k+2 = \Theta(\sqrt N)$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(6k^2+7k+2\) Pinned between $\mathrm{bs}$ and $\mathrm{C}$, which coincide at $(3k+2)(2k+1)$ here.
\(\deg(f)\) Exact degree \((3k+2)^2\) putative Degree is exactly multiplicative [Tal13]; $\deg(\mathrm{OR}_{3k+2}) = 3k+2$ and $\deg(g) = 3k+2$ (brute force gives $5$ at $k=1$ and $8$ at $k=2$; $g$ is a sum of $2k+1$ mutually exclusive subcube indicators of codimension $3k+2$, and their top monomials cannot all cancel). Note $\deg = \tfrac34 N + O(\sqrt N)$: the function is not of full degree, because each gadget leaves $k$ coordinates free. Tal13
\(\deg_2(f)\) Mod-2 degree \((3k+2)^2\) putative Over $\mathbb{F}_2$, $\mathrm{OR} = 1 + \prod_i(1+g_i)$ on disjoint blocks, so $\deg_2$ adds over the blocks; the gadget has $\deg_2(g) = \deg(g) = 3k+2$ (brute force at $k = 1,2$).
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(N)\) Between $\mathrm{C} = (3k+2)(2k+1)$ and $N = (3k+2)(4k+2)$ -- so between $N/2$ and $N$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N = 12k^2+14k+4\) Every variable is relevant, and a non-adaptive algorithm must read every relevant variable.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{fbs} \le \mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$, with $\mathrm{fbs} = \Theta(N)$ here.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{bs} \le \mathrm{R}_{\varepsilon} \le \mathrm{D}$, with both ends $\Theta(N)$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{bs} \le \mathrm{R}_0 \le \mathrm{D}$, with both ends $\Theta(N)$.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(N)\) Sandwiched: $\mathrm{fbs} \le \mathrm{RC} \le \mathrm{D}$, with both ends $\Theta(N)$.
\(\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^{3k+2}$. Upper: reading the blocks in turn multiplies the gadget's optimal tree size (exactly $13$ at $k=1$ and $30$ at $k=2$, i.e. $\mathrm{poly}(k)$) once per block, giving $k^{O(k)}$. Not pinned between the two.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(N)\) Between $\deg/2 = \Theta(N)$ and $\mathrm{D} = \Theta(N)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(\sqrt N),\ O(N)\) Between $\mathrm{Q} = \Omega(\sqrt N)$ and $\mathrm{D} = \Theta(N)$. The $\deg/2 = \Theta(N)$ floor pins $\mathrm{Q}_{\mathrm{E}}$ but not $\mathrm{Q}_0$, whose floor is $\mathrm{rdeg}/2$ -- and $\mathrm{rdeg}$ has only an upper bound here.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(N)\) A monochromatic subcube partition expresses $f$ as a signless sum of subcube indicators, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg$ and $\mathrm{D}$ are both $\Theta(N)$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(N)\) Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; see \(\mathrm{SP}(f)\).
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(N)\) Between $\mathrm{fbs}$ and $\mathrm{C}$, which coincide here.
\(\lambda(f)\) Spectral sensitivity \(3k+2\) putative Pinned exactly by $\sqrt{\deg} \le \lambda \le \mathrm{s}$ [ABKRT21]: $\deg = (3k+2)^2$ and $\mathrm{s} = 3k+2$. So $\mathrm{bs} = \tfrac23\lambda^2 - \tfrac13\lambda$ as well -- this function is also a near-extremal example for $\mathrm{bs}$ vs $\lambda$, the quantity later pushed past exponent $2$ by \(f_{\mathrm{Mei}}\).
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(k) = \Theta(\sqrt N)\) putative Lower: $\mathrm{C}_{\min} \le \mathrm{rank}$ gives $3k+2$. Upper: the gadget has $\mathrm{rank}(g) = 2$ (computed exactly for $k = 1,2$), and reading the blocks in turn grafts the remaining tree onto the $0$-leaves, so $\mathrm{rank} \le 2(3k+2)$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(6k^2+7k+2\) $\mathrm{FC} = \mathrm{fbs}$ by LP duality, and \(\mathrm{fbs}(f)\) is pinned at $(3k+2)(2k+1)$ here.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(N)\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (for $b=1$) or $1-f$ (for $b=0$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so nothing cancels and $\deg(f) \le \min\{\mathrm{UC}^0,\mathrm{UC}^1\} = \mathrm{UC}_{\min}$. Here $\deg = (3k+2)^2 = \Theta(N)$ and $\mathrm{UC} = \Theta(N)$, so both sides are pinned.
\(\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} = \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} = \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{CG}(f)\) Certificate game complexity (private coin) \(\Omega(N),\ O(N^{3/2})\) putative The private-coin certificate game is not capped by $\mathrm{D}$. Lower: $\mathrm{CG} \ge \mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(N)$. Upper: $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = (6k^2+7k+2)(3k+2) = \Theta(N^{3/2})$, the two sides being wildly asymmetric here. The $\mathrm{EC}$ route gives only $O(\mathrm{EC}^2) = O(N^2)$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \bar{\mathrm{R}}_{\varepsilon} \le \mathrm{R}_0$, with both ends $\Theta(N)$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(N)\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}^{1} \le \mathrm{R}_0$, with both ends $\Theta(N)$ here.
\(\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}^{*}(f) \ge \mathrm{bs}(f) = \Theta(N)$; and $\mathrm{R}^{*} \le \mathrm{R} = \Theta(N)$ by submultiplicativity. Composition is therefore perfect here for the trivial reason that $\mathrm{bs}$ and $\mathrm{R}$ already coincide.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(N)\) Sandwiched: $\mathrm{fbs} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with both ends $\Theta(N)$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(N)\)· Sandwiched: $\mathrm{fbs} \le \overline{\mathrm{prt}}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with both ends $\Theta(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).
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Not pinned. Lower: $\mathrm{Q} = \Omega(\lambda) = \Omega(3k+2) = \Omega(\sqrt N)$. Upper: $f$ is a DNF with $m = (3k+2)(2k+1) = \Theta(N)$ terms of width $w = 3k+2 = \Theta(\sqrt N)$, so robust Grover over the terms with a Grover $\mathrm{AND}_w$ inside each costs $O(\sqrt m\cdot\sqrt w) = O(k^{3/2})$ with no log overhead [HoyerMoscadeWolf03]. Equivalently, $\mathrm{Q}$ composes and $\mathrm{Q}(\mathrm{OR}_{3k+2}) = \Theta(\sqrt k)$ while $\mathrm{Q}(g) = O(k)$. Closing the gap needs the exact adversary bound of the gadget, exactly as for \(K^{\circ k}\). HoyerMoscadeWolf03 ABKRT21
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Lower: $\mathrm{Adv} \ge \sqrt{\mathrm{bs}} = \Theta(\sqrt N)$ (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\)). Upper: $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = O(N^{3/4})$. The certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = O(N^{3/4})$ gives the same ceiling. Ambainis02
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Omega(\sqrt N),\ O(N^{3/4})\) putative $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Omega(\sqrt N),\ O(N^{3/4})\) putative $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants; the window is that of \(\mathrm{Q}_{\varepsilon}(f)\).
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Lower: $\mathrm{bs} = O(\widetilde{\deg}^2)$ [NS94] with $\mathrm{bs} = \Theta(N)$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(N^{3/4})$. Either way $\widetilde{\deg}$ is strictly below $\deg = \Theta(N)$ unless the gadget's adversary bound is maximal. NS94
\(\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 $(3k+2)(2k+1)$ disjoint sensitive blocks; every unstarred bit is $0$ as usual, so finding a $\ast$ is unstructured search over those blocks.
\(\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} = \Omega(\sqrt N)$ and $\mathrm{R} = \Theta(N)$ here.
\(\mathrm{MaxInf}(f)\) Maximum influence \(\Theta(k\,2^{-3k})\) putative The $3k+2$ blocks are interchangeable and the gadget is invariant under the rotation $y_i \mapsto y_{i+2}$, whose two orbits (odd and even positions) carry $k+1$ and $2k+1$ of each firing pattern's $3k+2$ pinned coordinates. So single-coordinate influences vary by a factor $\le 2$ and $\max_i \mathrm{Inf}_i = \Theta(\mathrm{I}(f)/N) = \Theta(k^3 2^{-3k}/k^2)$. Exactly: an even position is pinned by all $2k+1$ patterns, giving $\mathrm{MaxInf} = 2(2k+1)2^{-(3k+2)}(1-p)^{3k+1}$. Well below the Aaronson-Ambainis threshold, as for every function here whose uniform measure is lopsided.
\(\mathrm{Var}(f)\) Variance \(\Theta(k^2 2^{-3k})\) $4p(1-p)$ at $p = 1-(1-(2k+1)2^{-(3k+2)})^{3k+2} = (1+o(1))(3k+2)(2k+1)2^{-(3k+2)}$.
\(\mathrm{osss}(f)\) OSSS number \(\Theta(k) = \Theta(\sqrt N)\) putative $\Theta(k^2 2^{-3k})$ over $\mathrm{MaxInf} = \Theta(k2^{-3k})$. Equal to $\mathrm{s} = 3k+2$ up to constants, and quadratically short of $\mathrm{D} = \Theta(N)$ -- the same picture as \(f_{\mathrm{Rub}}\), whose gadget structure this shares.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(k) = \Theta(\sqrt N)\) putative A firing pattern pins $3k+2$ coordinates, so $\mathrm{NS}_\delta = (2+o(1))p(1-(1-\delta)^{3k+2})$ crosses $\mathrm{Var}/4$ at $\delta^{*} = \Theta(1/k)$. Tight against $4\mathrm{s} = 4(3k+2)$.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(k^3 2^{-3k})\) putative For a Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$ -- the two differ only for bounded real-valued $p$. So this is the \(\mathrm{I}(f)\) entry verbatim.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(k^3 2^{-3k})\) putative Exactly $\mathrm{I}(f) = (3k+2)\,\mathrm{I}(g)(1-p)^{3k+1}$ with $p = (2k+1)2^{-(3k+2)}$ and $\mathrm{I}(g) = 2(3k+2)(2k+1)2^{-(3k+2)}$: a $1$-input of $g$ has exactly $3k+2$ sensitive bits and there are $(2k+1)2^{k}$ of them. Both formulas checked by exhaustive Fourier computation for $k \le 3$. Since $p(3k+2) \to 0$, the correction factor is $1-o(1)$ and $\mathrm{I}(f) = 2(3k+2)^2(2k+1)2^{-(3k+2)}(1-o(1)) = 2^{-\Theta(\sqrt N)}$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(6k^2+7k+2\) $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14], and $\mathrm{bs} = \mathrm{bs}^0 = 6k^2+7k+2$ is attained at the all-zeros input. 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)$, and repeating each query $O(\log \mathrm{R})$ times gives $O(\mathrm{R}\log \mathrm{R})$ [FRPU94]. FRPU94
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(N)\) $\mathrm{noisyR} \le \mathrm{R}$, and $\mathrm{R} = \Theta(N)$ is of the order of the arity, which forces equality up to constants by the recorded implication [CKMPSS23]. BenDavidBlais20composition CKMPSS23
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(\sqrt N),\ O(N^{3/4}\log N)\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt N)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05], with the recorded $\mathrm{Q} = O(N^{3/4})$. The window is inherited wholesale from the open $\mathrm{Q}$ window. BNRdW05
\(\chi(f)\) Conflict complexity \(\Theta(N)\) Pinned: $\chi = \Omega(\mathrm{bs}) = \Omega(6k^2) = \Omega(N)$ [Li18], and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(N)$. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(N)\) Between $\chi = \Omega(\mathrm{bs}) = \Omega(N)$ and $\mathrm{LR} \le \mathrm{R} = O(N)$ [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]: the extremal $\mathrm{s}$-vs-$\mathrm{bs}$ gadget is nonetheless a perfect inner function for composition. BBGM22
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(N)\) putative $\deg_2 \le \mathrm{D}^{\oplus} \le \mathrm{D}$, and the recorded $\deg_2 = (3k+2)^2 = \Theta(N)$ and $\mathrm{D} = \Theta(N)$ close the sandwich: parity queries buy nothing.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(\Theta(N)\) putative Fourier dimension is squeezed by $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}(f) \le N$, and the \(\mathrm{D}^{\oplus}(f)\) entry gives $\mathrm{D}^{\oplus} = \Theta(N)$.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\Theta(k^2 2^{-3k})\) putative For constant $\delta$, $\delta\,\mathrm{Var}(f) \le \mathrm{NS}_\delta(f) \le \tfrac12\mathrm{Var}(f)$, since every factor $1-(1-2\delta)^{|S|}$ with $|S|\ge 1$ lies in $[2\delta,1]$. The gadget has $\Pr[g=1] = (2k+1)2^{-(3k+2)}$ and $f$ is the $\mathrm{OR}$ of $3k+2$ disjoint copies (the same numbers that give the recorded $\mathrm{I}(f)$), so $\Pr[f=1] = \Theta(k^2 2^{-3k})$ and $\mathrm{Var} = 4p(1-p) = \Theta(k^2 2^{-3k})$. ODonnell14
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - \Theta(k^2 2^{-3k})\) putative From $\mathrm{Stab}_\rho = 1-2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: almost always $0$, hence almost perfectly noise stable.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\le 3k+2\) $\mathrm{ndeg} \le \mathrm{C}^1 = 3k+2$ (sum the $1$-certificate indicators, all with positive coefficients). Since $\deg = (3k+2)^2$, nondeterministic degree is at most $\sqrt{\deg}$ here -- the same quadratic collapse as in \(f_{\mathrm{Rub}}\). IJKKKSWW23
\(\mathrm{rdeg}(f)\) Rational degree \(\le 6k^2+7k+2\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \mathrm{C} = 6k^2+7k+2$ [IJKKKSWW23]; the $0$-side, with $\mathrm{C}^0 = 6k^2+7k+2$, is what dominates. IJKKKSWW23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(O(k) = O(\sqrt N)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil \le \lceil (3k+2)/2\rceil$ [deWolf03], from the \(\mathrm{ndeg}(f)\) entry. deWolf03
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(N^{3/4})\) $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(N^{3/4})$; the lower end of the recorded $\widetilde{\deg}$ window comes from $\mathrm{bs} = O(\widetilde{\deg}^2)$, which has no one-sided analogue.
\(\mathrm{sdeg}(f)\) Sign degree \(O(N^{3/4})\) From $\mathrm{sdeg} \le \widetilde{\deg} = O(N^{3/4})$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(N^{3/4})\) At most $\widetilde{\deg} = O(N^{3/4})$; the competing bound $\mathrm{rdeg} \le \mathrm{C} = \Theta(N)$ is weaker.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(N^{3/4})\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) \le O(\widetilde{\deg}) = O(N^{3/4})$ [MahadevdeWolf15]. 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. 1 in total.

Separations it witnesses

Cited as a witness by

Notes

[AmbainisSun11] also show the construction is optimal within its strategy: for any gadget $g$ with $\mathrm{s}^0(g) = 1$ and $\mathrm{bs}^0(g) = k$ one has $\mathrm{s}^1(g) \ge 3(k-1)/2$, so composing OR with such a $g$ can never beat $\mathrm{bs} = (\tfrac23 + o(1))\mathrm{s}^2$. Any further improvement must use a gadget with $\mathrm{s}^0(g) > 1$.