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

Low-sensitivity function from unambiguous certificates

The current record for D-vs-s: $\mathrm{D} = \widetilde\Omega(\mathrm{s}^3)$.

total separating 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

MeasureValueNotes
\(\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.

… and 15 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

Cited as a witness by

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}}\).