Low-sensitivity function from unambiguous certificates
The current record for D-vs-s: $\mathrm{D} = \widetilde\Omega(\mathrm{s}^3)$.
total arity: $\mathrm{poly}(n)$ bits
Description
Built from a function with small unambiguous certificate complexity by a composition that keeps sensitivity low while forcing deterministic (and quantum) algorithms to work hard.
Formal definition
Two ingredients [BHT17]. Desensitizing: replace each input bit $x_i$ of $f$ by three bits and accept only strings of the form $ppp$ for $p$ an unambiguous $1$-certificate; the result $f'$ has $\mathrm{s}_0(f')\le 1$ and $\mathrm{s}_1(f')\le 3\,\mathrm{UC}_1(f)$, while no measure in $\{\mathrm{D},\mathrm{R},\mathrm{Q},\mathrm{C},\mathrm{bs},\mathrm{RC}, \mathrm{UC},\deg\}$ decreases. Amplifying: compose on the outside with $\mathrm{OR}_{3\mathrm{UC}_{\min}(f)}$ (for $\mathrm{D}$) or with $\mathrm{BSum}_{\mathrm{UC}_{\min}(f)}$, Block $k$-sum (for $\mathrm{Q}$), both of which have certificates using only $O(\mathrm{polylog})$ ones, so that $\mathrm{s}(\hat f)=\widetilde O(\mathrm{UC}_{\min}(f))$ while the outer complexity multiplies through. Throughout the table below, $f$ is the base function, $f'$ is its desensitized version, and $\hat f := \mathrm{BSum}_n \circ f'$ with $n = \mathrm{UC}_{\min}(f)$ is the amplified function whose values are recorded.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{s}(f)\) Sensitivity | \(\widetilde O(n)\) | Every sensitive bit of $\hat f = \mathrm{BSum}_n\circ f'$ lies in a block that is sensitive for the outer Block $k$-sum, and Block $k$-sum has certificates containing only $O(\log^3 n)$ ones; with $\mathrm{s}_0(f')\le 1$ this gives $\mathrm{s}(\hat f)\le n\,\mathrm{s}_0(f')+O(\log^3 n)\,\mathrm{s}_1(f')=\widetilde O(n)$ [BHT17, Thm 3]. BHT17 |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\widetilde\Omega(n^3)\) | Quantum query complexity is multiplicative under composition, so $\mathrm{Q}(\hat f)=\widetilde\Omega(n\cdot\mathrm{Q}(f))$; with the base $\mathrm{BKK}_{\mathrm{CS}}$ contributing $\mathrm{Q}(f)=\widetilde\Omega(n^2)$ this is $\widetilde\Omega(n^3)$ [BHT17, Cor. 2]. BHT17 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{R}\ge\mathrm{Q}$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{R}_0\ge\mathrm{R}\ge\mathrm{Q}$. |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{D}\ge\mathrm{R}_0\ge\mathrm{Q}$. This is the recorded $\mathrm{D}=\widetilde\Omega(\mathrm{s}^3)$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}$. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{R}^1\ge\mathrm{R}\ge\mathrm{Q}$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\widetilde\Omega(n^{3/2})\) | The sabotage inequality runs $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], i.e. $\mathrm{RS}=O(\mathrm{R})$, so the recorded $\mathrm{R}=\widetilde\Omega(n^3)$ gives no floor. What does: $\mathrm{R}=O(\mathrm{RS}^2\log\mathrm{RS})$ for total $f$ [Thm 32], hence $\mathrm{RS}=\widetilde\Omega(\sqrt{\mathrm{R}})=\widetilde\Omega(n^{3/2})$; the weaker $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}$ only gives $\widetilde\Omega(n)$. Since no total function with $\mathrm{RS}=o(\mathrm{R})$ is known, the truth is probably $\widetilde\Theta(n^3)$, but that is not a theorem. BenDavidKothari18 |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\widetilde\Omega(n^3)\) | The general adversary bound characterises bounded-error quantum query complexity, $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$, so it inherits the recorded $\mathrm{Q}$. Reichardt11 |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\widetilde\Omega(n^3)\) | The approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}$, hence $\Theta(\mathrm{Q})$. LMRSS11 |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{Adv}^{\pm}\le\mathrm{MAdv}$. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\widetilde\Omega(n^{3/2})\) putative | From $\mathrm{D}\le\mathrm{C}^2$ against $\mathrm{D}=\widetilde\Omega(n^3)$. No matching upper bound is known here: all that totality gives is $\mathrm{C}\le\mathrm{s}\cdot\mathrm{bs}$ [Nisan91], and the only theorem bounding $\mathrm{bs}$ by $\mathrm{s}$ is $\mathrm{bs}\le 2\deg^2\le 2\mathrm{s}^4$ (Nisan-Szegedy plus Huang), giving $\mathrm{C}\le 2\mathrm{s}^5=\widetilde O(n^5)$. The familiar $\mathrm{bs}\le\mathrm{s}^2$ is an open conjecture, not an available bound. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\mathrm{UC}\ge\mathrm{C}$; equivalently $\mathrm{D}\le\mathrm{UC}^2$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\mathrm{SP}\ge\mathrm{C}$; equivalently $\mathrm{D}\le\mathrm{SP}^2$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\widetilde\Omega(n)\) putative | From $\mathrm{D}\le\mathrm{s}\cdot\mathrm{bs}^2$ with the recorded $\mathrm{s}=\widetilde O(n)$ and $\mathrm{D}=\widetilde\Omega(n^3)$: $\mathrm{bs}\ge\sqrt{\mathrm{D}/\mathrm{s}}=\widetilde\Omega(n)$. So the low-sensitivity function is not low-block-sensitivity: $\mathrm{bs}$ is already as large as $\mathrm{s}$. The available ceiling is $\mathrm{bs}\le 2\deg^2\le 2\mathrm{s}^4=\widetilde O(n^4)$ (Nisan-Szegedy composed with Huang's $\deg\le\mathrm{s}^2$); $\mathrm{bs}\le\mathrm{s}^2$ would give $\widetilde O(n^2)$ but is still conjectural. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{fbs}\ge\mathrm{bs}$. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17 |
| \(\deg(f)\) Exact degree | \(\widetilde\Omega(n)\) putative | From $\mathrm{D}=O(\deg^3)$ [Midrijanis04] against $\mathrm{D}=\widetilde\Omega(n^3)$. Huang caps it at $\deg\le\mathrm{s}^2=\widetilde O(n^2)$. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\widetilde\Omega(n^{3/4})\) putative | From $\mathrm{D}=O(\widetilde{\deg}^4)$ [ABKRT21] against $\mathrm{D}=\widetilde\Omega(n^3)$. |
| \(\lambda(f)\) Spectral sensitivity | \(\widetilde O(n)\) | Squeeze: $\lambda\le\mathrm{s}=\widetilde O(n)$. Spectral sensitivity is therefore small here too, which is why this family also witnesses a large $\mathrm{D}$-vs-$\lambda$ gap. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(\widetilde O(n)\) | Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde O(n)$. The desensitizing step is what makes both sides small: the inner $f'$ has $\mathrm{s}_0(f')\le 1$ by construction. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(\widetilde O(n)\) | Squeeze: $\mathrm{s}_1\le\mathrm{s}=\widetilde O(n)$; the outer Block $k$-sum contributes only $O(\log^3 n)$ ones per certificate. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(\widetilde O(n)\) | Squeeze: $\mathrm{I}(f)=\mathbf{E}_x[\mathrm{s}(f,x)]\le\mathrm{s}(f)=\widetilde O(n)$. Combined with $\mathrm{D}=\widetilde\Omega(n^3)$ this is a cubic $\mathrm{D}$-vs-$\mathrm{I}$ gap that tracks the record $\mathrm{D}$-vs-$\mathrm{s}$ gap exactly. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(\widetilde O(n)\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=\widetilde O(n)$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\mathrm{D}=O(\mathrm{UC}_{\min}^2)$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^3)$. Note this is the output of the amplification, not the $\mathrm{UC}_{\min}$ of the base function that sets the scale variable. BHT17 |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\mathrm{R}_0=O(\mathrm{EC}^2)$ against $\mathrm{R}_0=\widetilde\Omega(n^3)$. This beats the bare $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(n)$ by half a power. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Omega(n^3)$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{Q}_0\ge\mathrm{Q}$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$ with $\mathrm{fbs}=\widetilde\Omega(n)$. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(\widetilde\Omega(n)\) | For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\widetilde\Omega(n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)). |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\widetilde\Omega(n^3)\) | For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Omega(n^3)$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\widetilde\Omega(n^3)\) | The distributional form of $\mathrm{R}$: $\overline{\mathrm{R}}=\Theta(\mathrm{R})=\widetilde\Omega(n^3)$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\widetilde\Omega(n^3)\) | Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde\Omega(n^3)$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{D}\le\mathrm{DTsize}-1$, so the tree needs at least $\widetilde\Omega(n^3)$ leaves. Only the trivial size bound is claimed -- the exponential lower bound one would expect is not established here. |
| \(\chi(f)\) Conflict complexity | \(\widetilde\Omega(n^{3/2})\) | Floor from $\mathrm{R}=O(\chi^2)$ [Sanyal18] against $\mathrm{R}=\widetilde\Omega(n^3)$. This beats the block-sensitivity floor $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(n)$ [Li18] by half a power. Sanyal18 Li18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\bar\chi=\Omega(\mathrm{RS})=\widetilde\Omega(n^{3/2})$ along the chain $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]; equivalently $\bar\chi=\Omega(\sqrt{\mathrm{R}})$ directly. GLSS19 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\mathrm{LR}\ge\bar\chi=\widetilde\Omega(n^{3/2})$, equivalently $\mathrm{LR}=\Omega(\sqrt{\mathrm{R}})$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\widetilde\Omega(n^3)\) | Unlike the classical relaxations above, this one is pinned at the top by the quantum floor $\mathrm{R}^*\ge\Omega(\mathrm{Q})=\widetilde\Omega(n^3)$, and $\mathrm{R}^*\le\mathrm{R}$ costs nothing since $\mathrm{R}$ is itself only bounded below. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{N}_p\ge\mathrm{R}=\widetilde\Omega(n^3)$; the $O(\mathrm{R}\log\mathrm{R})$ ceiling adds nothing because $\mathrm{R}$ has no recorded ceiling. FRPU94 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}=\widetilde\Omega(n^3)$ [BNRdW05]. BNRdW05 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\widetilde\Omega(n)\) | The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(n)$ for total functions [ABIKPS17]. Against the recorded $\mathrm{CG}=\widetilde\Omega(n^3)$ this cell is where the private-coin/public-coin gap would show, but only the two floors are known. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\widetilde\Omega(n)\) | Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(n)$. ABIKPS17 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\widetilde\Omega(n)\) | Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\widetilde\Omega(n)$. ABIKPS17 |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\widetilde\Omega(n)\) | Two floors coincide: $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(n)$, and $\mathrm{D}=O(\mathrm{prt}_{1/3}^3)$ against $\mathrm{D}=\widetilde\Omega(n^3)$ gives $\widetilde\Omega(n)$ as well [JainKlauck10]. No ceiling, since $\mathrm{prt}\le 2\mathrm{R}$ and $\mathrm{R}$ is unbounded above here. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\widetilde\Omega(n)\) | The $\mathrm{RC}$ floor survives the relaxation of the partition bound, so $\mathrm{rprt}=\widetilde\Omega(n)$ by the argument of the $\mathrm{prt}$ line. JainKlauck10 |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Omega(n)$. The certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}$ gives no ceiling here because neither one-sided certificate complexity is bounded above, and $\lambda\le\mathrm{Adv}$ gives no floor because $\lambda$ is only bounded above. Ambainis02 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\widetilde\Omega(n^{3/4})\) | Squeeze: $\mathrm{cjdeg}\ge\widetilde{\deg}=\widetilde\Omega(n^{3/4})$ (dropping non-negativity can only lower the degree). |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(\widetilde O(n)\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}=\widetilde O(n)$; equally $\mathrm{MaxInf}\le\mathrm{s}$. Against $\mathrm{D}=\widetilde\Omega(n^3)$ this is a cubic gap, i.e. the same record the $\mathrm{s}$ column records. |
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. 29 in total, strongest first.
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \widetilde\Omega(n^3)\) against \(\mathrm{s}(f) = \widetilde O(n)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) = \widetilde\Omega\big(\lambda(f_n)^{3}\big)\)from \(\mathrm{R}_{\varepsilon}(f) = \widetilde\Omega(n^3)\) against \(\lambda(f) = \widetilde O(n)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = \widetilde\Omega\big(\lambda(f_n)^{3}\big)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \widetilde\Omega(n^3)\) against \(\lambda(f) = \widetilde O(n)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{R}_{\varepsilon}(f) = \widetilde\Omega(n^3)\) against \(\mathrm{s}(f) = \widetilde O(n)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \widetilde\Omega(n^3)\) against \(\mathrm{s}(f) = \widetilde O(n)\)
-
\(\mathrm{R}^{1}(f_n) = \widetilde\Omega\big(\lambda(f_n)^{3}\big)\)from \(\mathrm{R}^{1}(f) = \widetilde\Omega(n^3)\) against \(\lambda(f) = \widetilde O(n)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) = \widetilde\Omega\big(\lambda(f_n)^{3}\big)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \widetilde\Omega(n^3)\) against \(\lambda(f) = \widetilde O(n)\)
-
\(\mathrm{R}^{1}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{R}^{1}(f) = \widetilde\Omega(n^3)\) against \(\mathrm{s}(f) = \widetilde O(n)\)
-
\(\mathrm{R}^{*}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{R}^{*}(f) = \widetilde\Omega(n^3)\) against \(\mathrm{s}(f) = \widetilde O(n)\)
-
\(\mathrm{N}_{p}(f_n) = \widetilde\Omega\big(\lambda(f_n)^{3}\big)\)from \(\mathrm{N}_{p}(f) = \widetilde\Omega(n^3)\) against \(\lambda(f) = \widetilde O(n)\)
-
\(\mathrm{R}^{*}(f_n) = \widetilde\Omega\big(\lambda(f_n)^{3}\big)\)from \(\mathrm{R}^{*}(f) = \widetilde\Omega(n^3)\) against \(\lambda(f) = \widetilde O(n)\)
-
\(\mathrm{N}_{p}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{N}_{p}(f) = \widetilde\Omega(n^3)\) against \(\mathrm{s}(f) = \widetilde O(n)\)
-
\(\mathrm{CG}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{CG}(f) = \widetilde\Omega(n^3)\) against \(\mathrm{s}(f) = \widetilde O(n)\)
-
\(\mathrm{psD}(S)(f_n) = \widetilde\Omega\big(\lambda(f_n)^{3}\big)\)from \(\mathrm{psD}(S) = \widetilde\Omega(n^3)\) against \(\lambda(f) = \widetilde O(n)\)
… and 15 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{D} = \widetilde\Omega(\mathrm{s}^3)$ against the upper bound $\mathrm{D}=O(\mathrm{s}^6)$ (Huang + Midrijanis).
-
$\mathrm{R}_0 = \widetilde\Omega(\mathrm{s}^3)$.
-
$\mathrm{R} = \widetilde\Omega(\mathrm{s}^3)$.
-
$\mathrm{Q} = \widetilde\Omega(\mathrm{s}^3)$.
-
$\mathrm{C} = \Omega(\mathrm{UC}_{\min}^{1.22})$.
Cited as a witness by
-
\(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^3\big)\)
Notes
The values describe the sensitivity-amplified function $\hat f=\mathrm{BSum}_n\circ f'$ of [BHT17, Thm 3, Cor. 2], which is what sets the $\mathrm{s}$ column. The last witness below, $\mathrm{C}=\Omega(\mathrm{UC}_{\min}^{1.22})$, comes from a different family in the same paper -- a projective-plane gadget with $\mathrm{C}=k^2-k+1$ and $\mathrm{UC}_{\min}=k(k+1)/2$ composed over a weighted alphabet [BHT17, Thm 5] -- so its numbers are not merged into the table above. Feeding that family through the same amplification is what gives $\mathrm{C}=\Omega(\mathrm{s}^{2.22})$ [BHT17, Cor. 4]; it has since been superseded by the cubic gap of \(f_{\mathrm{BBGJK}}\).