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

Unambiguous-DNF / Alon-Saks-Seymour function

Sets the C row: $\mathrm{C}=\widetilde\Omega(\mathrm{s}^3)$, $\widetilde\Omega(\lambda^4)$, $\widetilde\Omega(\deg^2)$, $\widetilde\Omega(\widetilde{\deg}^3)$.

total separating arity: $\widetilde\Theta(n^4)$ bits

Description

Comes from the resolution of the Alon-Saks-Seymour problem via unambiguous DNFs: a total function whose certificate complexity is much larger than its unambiguous certificate complexity, sensitivity, degree and spectral sensitivity.

Formal definition

Two stages [BBGJK21]. First a partial function $\mathrm{Eah}_n\colon\{0,1\}^{O(n^2)}\to\{0,1,*\}$ with $\mathrm{C}(\mathrm{Eah}_n)\le\widetilde O(n)$ but a $*$-input $z$ at which both one-sided certificate complexities are $\ge\Omega(n^2)$ (this is their "Puzzle II", solved by 2-colouring an intersecting hypergraph). Then a cheat-sheet-style totalisation: take $k=\log N$ copies of the partial function, use their outputs to index one of $2^k$ array cells, and require that cell to hold identification numbers of certificates actually present in the copies. The result is a total $g\colon\{0,1\}^{3N^2\log^2 N}\to\{0,1\}$, $N=O(n^2)$, with $\mathrm{C}_0(g)\ge\min\{\mathrm{C}_0(\mathrm{Eah},z), \mathrm{C}_1(\mathrm{Eah},z)\}$ and $\mathrm{UC}_1(g)\le 3\,\mathrm{C}(\mathrm{Eah})\log^2 N$ [BBGJK21, Sec. 5.1].

Measure values

MeasureValueNotes
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\widetilde\Theta(n^2)\) Lower bound $\Omega(n^2)$ at the all-copies-are-$z$ input [BBGJK21, Claim 16]: a cheaper certificate can neither pin down the $\mathrm{Eah}$-values nor touch every array cell. Upper bound from $\mathrm{C}_0\le\mathrm{D}=\widetilde O(n^2)$. BBGJK21
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\widetilde\Theta(n)\) Upper: $\mathrm{UC}_{\min}\le\mathrm{UC}_1\le 3\,\mathrm{C}(\mathrm{Eah}_n)\log^2 N=\widetilde O(n)$ [BBGJK21, Claim 17] -- read one certificate per copy plus the whole indexed cell. Lower: $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^2)$. BBGJK21
\(\mathrm{D}(f)\) Deterministic query complexity \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{D}\ge\mathrm{C}_0=\widetilde\Omega(n^2)$ and $\mathrm{D}\le\mathrm{UC}_{\min}^2=\widetilde O(n^2)$ [BHT17]. So the quadratic $\mathrm{C}_0$-vs-$\mathrm{UC}_1$ gap is simultaneously a quadratic $\mathrm{D}$-vs-$\mathrm{UC}_{\min}$ gap, and both are optimal up to logs.
\(\mathrm{C}(f)\) Certificate complexity \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\ge\mathrm{C}_0$ and $\mathrm{C}\le\mathrm{D}$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\widetilde O(n)\) Squeeze: $\mathrm{C}_1\le\mathrm{UC}_1=\widetilde O(n)$. The recorded $\mathrm{C}_0$ is quadratically larger -- this is the unambiguous-DNF-vs-CNF-width statement of [BBGJK21, Thm 1], matching the folklore $\mathrm{C}_0\le\mathrm{UC}_1^2$.
\(\deg(f)\) Exact degree \(\widetilde O(n)\) Summing the indicator polynomials of an unambiguous $1$-DNF represents $g$ exactly, so $\deg\le\mathrm{UC}_1=\widetilde O(n)$; against $\mathrm{C}=\widetilde\Omega(n^2)$ this is [BBGJK21, Cor. 4], improving the classical power-$1.63$ separation of [NW95]. BBGJK21
\(\mathrm{s}(f)\) Sensitivity \(\widetilde\Theta(n^{2/3})\) The recorded witness is $\mathrm{C}=\widetilde\Omega(\mathrm{s}^3)$ with $\mathrm{C}=\widetilde\Theta(n^2)$, which gives $\mathrm{s}=\widetilde O(n^{2/3})$; and the separation is only the recorded $\mathrm{C}$-vs-$\mathrm{s}$ exponent if $\mathrm{s}$ is no smaller, so $\widetilde\Theta$. (The tempting shortcut $\mathrm{C}\le\mathrm{s}\cdot\mathrm{bs}\le\mathrm{s}^3$ is not available: $\mathrm{bs}\le\mathrm{s}^2$ is the conjecture; what [Huang19] proves is $\mathrm{bs}\le\mathrm{s}^4$.) BBGJK21
\(\mathrm{bs}(f)\) Block sensitivity \(\widetilde\Omega(n^{4/3})\) putative From Nisan's $\mathrm{C}\le\mathrm{s}\cdot\mathrm{bs}$ [Nisan91] with $\mathrm{C}=\widetilde\Theta(n^2)$ and $\mathrm{s}=\widetilde\Theta(n^{2/3})$. No matching upper bound is available: that would need $\mathrm{bs}\le\mathrm{s}^2$, which is open -- [Huang19] gives only $\mathrm{bs}\le\mathrm{s}^4$. The ceiling here is the trivial $\mathrm{bs}\le\mathrm{C}=\widetilde O(n^2)$. If $\mathrm{bs}$ did sit at $\widetilde\Theta(n^{4/3})$ this family would also be an extremal $\mathrm{bs}=\widetilde\Theta(\mathrm{s}^2)$ example.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{fbs}\ge\mathrm{bs}$. The ceiling is $\mathrm{fbs}\le\mathrm{C}=\widetilde O(n^2)$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{R}=\Omega(\mathrm{fbs})$; the ceiling is $\mathrm{R}\le\mathrm{D}=\widetilde\Theta(n^2)$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$ and both ends are $\widetilde\Theta(n^2)$. A zero-error algorithm outputs a certificate, so certificate complexity is a lower bound on $\mathrm{R}_0$ even when it is far above $\mathrm{R}$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\widetilde\Omega(n^{4/3})\) The sabotage inequality runs the other way from what one might expect: $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{RS}=O(\mathrm{R})=\widetilde O(n^2)$ is the ceiling. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(n^{4/3})$, which happens to coincide with the recorded $\mathrm{R}$ floor. BenDavidKothari18
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\widetilde\Omega(n^{4/3})$. The ceiling is $\mathrm{Q}\le\mathrm{D}=\widetilde O(n^2)$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\widetilde O(n^{2/3})\) From the recorded witness $\mathrm{C}=\widetilde\Omega(\widetilde{\deg}^3)$ against $\mathrm{C}=\widetilde\Theta(n^2)$. Matched from below by $\widetilde{\deg}=\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{2/3})$, so the value is in fact tight. BBGJK21
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\widetilde\Omega(n^2)\) Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$; the ceiling is the arity $\widetilde\Theta(n^4)$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n^{4/3})$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\widetilde O(n)\) Squeeze: $\mathrm{C}_{\min}\le\mathrm{C}^1\le\mathrm{UC}_1=\widetilde O(n)$ -- every $1$-input is cheap to certify, and the hardness lives entirely on the $0$-side.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\widetilde\Omega(n^{4/3})\) putative Nisan's refined bound $\mathrm{C}^0\le\mathrm{s}_1\cdot\mathrm{bs}_0$ [Nisan91] with $\mathrm{C}^0=\widetilde\Theta(n^2)$ and $\mathrm{s}_1\le\mathrm{s}=\widetilde\Theta(n^{2/3})$. This pins the large block sensitivity to the $0$-side, matching the fact that $\mathrm{C}^0$ rather than $\mathrm{C}^1$ is what is large.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde\Theta(n^{2/3})$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{s}_1\le\mathrm{s}=\widetilde\Theta(n^{2/3})$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(n^{4/3})$; the ceiling is $\mathrm{EC}\le\mathrm{C}=\widetilde\Theta(n^2)$. (The alternative route $\mathrm{R}_0=O(\mathrm{EC}^2)$ only gives $\widetilde\Omega(n)$.)
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\widetilde\Omega(n^2)\) Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Theta(n^2)$; the ceiling is $\mathrm{CG}\le\mathrm{C}^0\mathrm{C}^1=\widetilde O(n^3)$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\widetilde\Omega(n^{4/3})\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\widetilde\Omega(n^{4/3})$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\widetilde\Omega(n^{4/3})\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Omega(n^{4/3})$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\widetilde\Omega(n^{4/3})\) The distributional form of $\mathrm{R}$: $\overline{\mathrm{R}}=\Theta(\mathrm{R})=\widetilde\Omega(n^{4/3})$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\widetilde\Omega(n^{4/3})\) Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde\Omega(n^{4/3})$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}=\widetilde\Omega(n^{2/3})$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\widetilde\Theta(n^2)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\widetilde\Omega(n^{2/3})\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\widetilde O(n^{2/3})\) Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{2/3})$, inheriting the caveat on the $\widetilde{\deg}$ line.
\(\mathrm{sdeg}(f)\) Sign degree \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{2/3})$, inheriting the caveat on the $\widetilde{\deg}$ line.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde\Theta(n^{2/3})$. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this makes the family a cubic $\mathrm{C}$-vs-$\mathrm{I}$ example, mirroring its record $\mathrm{C}$-vs-$\mathrm{s}$ gap.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\widetilde O(n^{2/3})\) 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^{2/3})$.
\(\mathrm{MaxInf}(f)\) Maximum influence \(\widetilde O(n^{2/3})\) A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}\le\mathrm{s}=\widetilde\Theta(n^{2/3})$. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this is a cubic $\mathrm{C}$-vs-$\mathrm{MaxInf}$ gap.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\widetilde O(n)\) Squeeze: $\mathrm{bs}_1\le\mathrm{C}^1\le\mathrm{UC}_1=\widetilde O(n)$. Read against the recorded $\mathrm{bs}_0=\widetilde\Omega(n^{4/3})$ this makes the block sensitivity of this family genuinely one-sided: all of it lives on the $0$-inputs, exactly like $\mathrm{C}$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{R}_0$, i.e. between $\widetilde\Omega(n^{4/3})$ and $\widetilde\Theta(n^2)$.
\(\chi(f)\) Conflict complexity \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Floor $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(n^{4/3})$ [Li18] (the alternative $\chi=\Omega(\sqrt{\mathrm{R}})$ only gives $\widetilde\Omega(n^{2/3})$); ceiling $\chi=O(\mathrm{R})=\widetilde O(n^2)$. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19] between $\mathrm{RS}=\widetilde\Omega(n^{4/3})$ and $\mathrm{R}=\widetilde O(n^2)$. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeezed between $\bar\chi=\widetilde\Omega(n^{4/3})$ and $\mathrm{R}=\widetilde O(n^2)$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeezed between $\mathrm{LR}=\widetilde\Omega(n^{4/3})$ and $\mathrm{R}=\widetilde O(n^2)$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\widetilde\Omega(n^{2/3})$ is weaker.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$, so the noisy model inherits the whole $\mathrm{R}$ range $[\widetilde\Omega(n^{4/3}),\widetilde O(n^2)]$. FRPU94
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\widetilde\Omega(n^{2/3}),\ \widetilde O(n^2)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range. BNRdW05
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$ for total functions [ABIKPS17], whose recorded range is $[\widetilde\Omega(n^{4/3}),\widetilde O(n^2)]$; independently $\mathrm{CG}^{\mathrm{pub}}\le\mathrm{C}=\widetilde\Theta(n^2)$. ABIKPS17
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(n^{4/3})$; ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n^2)$ [JainKlauck10, Thm 3.1]. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) The $\mathrm{RC}$ floor survives the relaxation and $\mathrm{rprt}\le\mathrm{prt}$, so the $\mathrm{prt}$ range carries over unchanged. JainKlauck10
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\widetilde\Omega(n^{2/3}),\ \widetilde O(n^{3/2})\) Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Omega(n^{4/3})$. Ceiling: the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\widetilde\Theta(n^2)\cdot\widetilde O(n)}=\widetilde O(n^{3/2})$. The strong asymmetry of the certificate complexities is what makes the barrier bite here. Ambainis02
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\widetilde\Omega(n^{2/3}),\ \widetilde O(n^2)\) Floor $\mathrm{cjdeg}\ge\widetilde{\deg}=\widetilde\Theta(n^{2/3})$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\widetilde\Theta(n^2)$, since a depth-$\mathrm{D}$ decision tree is an exact conical junta of width $\mathrm{D}$.
\(\mathrm{rdeg}(f)\) Rational degree \(\widetilde O(n)\) Squeeze: $\mathrm{rdeg}=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}\le\deg=\widetilde O(n)$. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this inherits the $\mathrm{C}$-vs-$\deg$ quadratic gap.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\widetilde O(n)\) Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(n)$; here the two bounds happen to agree, both coming from $\mathrm{UC}_1$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\widetilde O(n)\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(n)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{rdeg}_{1/3}\le\min\{\mathrm{rdeg},\widetilde{\deg}\}=\widetilde O(n^{2/3})$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this is a cubic $\mathrm{C}$-vs-$\mathrm{PostQ}$ gap. MahadevdeWolf15
\(\deg_2(f)\) Mod-2 degree \(\widetilde O(n)\) The exact multilinear representation over $\mathbb{R}$ has integer coefficients, so reducing mod $2$ gives $\deg_2\le\deg=\widetilde O(n)$.
\(\deg_p(f)\) Mod-p degree \(\widetilde O(n)\) Same integrality argument as the $\deg_2$ line, for every prime $p$.
\(\mathrm{DTsize}(f)\) Decision tree size \(\widetilde\Omega(n^2)\) Squeeze: $\mathrm{D}\le\mathrm{DTsize}-1$ with $\mathrm{D}=\widetilde\Theta(n^2)$. The stronger $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$ route is unavailable: $\mathrm{C}_{\min}=\widetilde O(n)$ is only an upper bound, so $\mathrm{rank}$ has no recorded floor.

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. 21 in total, strongest first.

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

Separations it witnesses

Notes

Why no $\lambda$ value is recorded. It is tempting to read $\lambda = \widetilde O(\sqrt n)$ off the $\mathrm{C}=\widetilde\Omega(\lambda^4)$ witness, exactly as the $\widetilde{\deg}$ and $\mathrm{s}$ values are read off theirs. But the four separations above are the four cells of the $\mathrm{C}$ row of [BBGJK21], and nothing in the statement forces them to be witnessed by one function. If they were, then $\lambda=\widetilde O(\sqrt n)$ together with the (solid) $\mathrm{bs}=\widetilde\Omega(n^{4/3})$ below would give $\mathrm{bs}=\widetilde\Omega(\lambda^{8/3})$ -- a power $2.67$, comfortably past the best known $\mathrm{bs}$-vs-$\lambda$ separation of $\lambda^{2.127}$ (see \(f_{\mathrm{Mei}}\)). A record that cheap would not have gone unnoticed, so the honest reading is that the $\mathrm{C}$-vs-$\mathrm{s}$ and $\mathrm{C}$-vs-$\lambda$ cells come from different constructions in the paper, and $\lambda$ for this function stays blank until the construction is transcribed. The same caution applies, more weakly, to reading the $\deg$ and $\widetilde{\deg}$ values off their witnesses.