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 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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{C}^0(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{C}^0(f) = \widetilde\Theta(n^2)\) against \(\mathrm{s}(f) = \widetilde\Theta(n^{2/3})\)
-
\(\mathrm{UC}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{2}\big)\)from \(\mathrm{UC}(f) = \widetilde\Theta(n^2)\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{UC}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^{3}\big)\)from \(\mathrm{UC}(f) = \widetilde\Theta(n^2)\) against \(\mathrm{s}(f) = \widetilde\Theta(n^{2/3})\)
-
\(\mathrm{bs}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{bs}(f) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{fbs}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{fbs}(f) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{RC}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{RC}(f) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{EC}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{EC}(f) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{FC}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{FC}(f) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{bs}^0(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{bs}^0(f) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{cbs}(S)(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{cbs}(S) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{RS}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{RS}(f) = \widetilde\Omega(n^{4/3})\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\chi(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\chi(f) = \widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\bar{\chi}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\bar{\chi}(f) = \widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
-
\(\mathrm{LR}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{1.3333}\big)\)from \(\mathrm{LR}(f) = \widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(n)\)
… and 7 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{C} = \widetilde\Omega(\mathrm{s}^3)$; upper bound $\mathrm{C}\le \mathrm{s}\cdot\mathrm{bs} \le 2\mathrm{s}^5$.
-
$\mathrm{C} = \widetilde\Omega(\lambda^4)$; upper bound $\mathrm{C}\le\mathrm{D}=O(\lambda^6)$.
-
$\mathrm{C} = \widetilde\Omega(\deg^2)$; upper bound $\mathrm{C}\le\mathrm{D}=O(\deg^3)$.
-
$\mathrm{C} = \widetilde\Omega(\widetilde{\deg}^3)$; upper bound $\mathrm{C}\le\mathrm{D}=O(\widetilde{\deg}^4)$.
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.