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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{CG}^{*}(f_n) = \Omega\big(\mathrm{s}(f_n)^{2}\big)\)from \(\mathrm{CG}^{*}(f) = \Theta(N)\) against \(\mathrm{s}(f) = n = \sqrt N\)
-
\(\mathrm{CG}^{\mathrm{ns}}(f_n) = \Omega\big(\mathrm{s}(f_n)^{2}\big)\)from \(\mathrm{CG}^{\mathrm{ns}}(f) = \Theta(N)\) against \(\mathrm{s}(f) = n = \sqrt N\)
Separations it witnesses
-
$\mathrm{bs}(f) = \tfrac12 \mathrm{s}(f)^2$; improved constant $\mathrm{bs}\ge\tfrac23 \mathrm{s}^2 - \tfrac13\mathrm{s}$ by [AmbainisSun11].
-
$\mathrm{RC} = \Omega(\mathrm{s}^2)$ (since $\mathrm{RC}=\Theta(\mathrm{fbs})\ge\mathrm{bs}$); the witness in the RC-vs-s and bs-vs-s cells.
Cited as a witness by
-
\(\mathrm{bs}(f_n) \ge \tfrac12\,\mathrm{s}(f_n)^2\)
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.