Cheat-sheet functions
A generic transformation turning a partial-function separation into a total-function separation.
total arity: $\mathrm{poly}(n)$ bits
Description
Given a partial function $f$ on $n$ bits, the cheat-sheet version $f_{\mathrm{CS}}$ takes $c$ independent inputs $x^1,\dots,x^c$ to $f$ plus $2^c$ "cheat-sheet" cells; the cell indexed by the string $f(x^1)\cdots f(x^c)$ is required to contain certificates for all $c$ answers. This makes the function total (an input that violates the promise simply fails to be certified) while preserving the cheap upper bound (solve all $c$ instances, look up the cell, verify) and the expensive lower bound.
Formal definition
See [ABK16, Definition 4]. Roughly: with $c = \Theta(\log n)$ copies, $\mathrm{Q}(f_{\mathrm{CS}}) = \widetilde\Theta(\mathrm{Q}(f) + \text{(certificate verification)})$ and $\mathrm{R}(f_{\mathrm{CS}}) = \widetilde\Omega(\mathrm{R}(f))$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\widetilde\Theta(n)\) | For $\mathrm{BKK}$: $\mathrm{Q}=\Omega(n/\log^5 n)$ by reduction from $k$-sum plus the quantum composition theorem [ABK16, Thm 10], and $\mathrm{Q}\le n$ trivially. The cheat sheet inherits it, $\mathrm{Q}(f_{\mathrm{CS}})=\Omega(\mathrm{Q}(f))$ [ABK16, Lem. 12], with a matching $\widetilde O(n)$ algorithm (solve the $10\log n$ copies, then read the indexed cell). ABK16 |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\widetilde\Theta(n)\) | Squeeze between $\mathrm{Q}=\widetilde\Omega(n)$ and $\mathrm{D}=\widetilde O(n)$. |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{D}\ge\mathrm{Q}=\widetilde\Omega(n)$, and $\mathrm{D}\le\mathrm{C}^2=\widetilde O(n)$ for a total function. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\widetilde O(\sqrt n)\) | The point of the construction: the outer Block $k$-sum has certificates made of $O(n)$ ones and only $O(k^2\log n)$ zeroes, and the inner $k$-sum certifies ones cheaply, so the composition certifies in $O(k^2\sqrt n\log n)=\widetilde O(\sqrt n)$ bits [ABK16, Thm 10]. The cheat sheet keeps this: certify the $10\log n$ copies and read the one indexed cell. ABK16 |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\widetilde\Theta(\sqrt n)\) | Upgraded from the bare $\mathrm{bs}\le\mathrm{C}$ upper bound: $\mathrm{D}\le\mathrm{C}\cdot\mathrm{bs}$ with $\mathrm{C}=\widetilde O(\sqrt n)$ and $\mathrm{D}=\widetilde\Omega(n)$ forces $\mathrm{bs}=\widetilde\Omega(\sqrt n)$ as well. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, which coincide here. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$, now pinned on both sides. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a quadratic $\mathrm{Q}$-vs-$\mathrm{CA}$ gap. ABIKPS17 |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\widetilde\Theta(n^{1/4})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. Quantum certificate complexity is a fourth power below $\mathrm{Q}$ here. |
| \(\mathrm{s}(f)\) Sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$, with the Huang floor $\mathrm{s}\ge\sqrt{\mathrm{bs}}=\widetilde\Omega(n^{1/4})$. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{Q}\le\mathrm{R}\le\mathrm{D}$, both $\widetilde\Theta(n)$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{R}\le\mathrm{R}_0\le\mathrm{D}$. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{D}$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | The 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})=\widetilde O(n)$, not the other way round. Floors: $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$, and $\mathrm{R}=O(\mathrm{RS}^2\log\mathrm{RS})$ for total $f$ [Thm 32] gives the same $\widetilde\Omega(\sqrt n)$. Pinning this cell would settle whether sabotage sees cheat-sheet hardness. BenDavidKothari18 |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\widetilde\Theta(n)\) | Maximised over input distributions: Yao's minimax gives $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})$. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. The adversary bound therefore does see the hardness that $\widetilde{\deg}$ misses -- this is the standard reading of the $\mathrm{Q}$-vs-$\widetilde{\deg}$ separation. Reichardt11 |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\widetilde\Theta(n)\) | Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11 |
| \(\deg(f)\) Exact degree | \(\widetilde O(\sqrt n)\) | For $\mathrm{BKK}_{\mathrm{CS}}$ [ABK16, Thm 4]. A $1$-input has a unique valid cheat-sheet location $\ell$, so the exact representing polynomial is the plain sum over $\ell$ of the degree-$\widetilde O(\sqrt n)$ polynomials representing "the certificate stored at $\ell$ checks out". ABK16 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\widetilde O(\sqrt n)\) | Squeeze: $\widetilde{\deg}\le\deg=\widetilde O(\sqrt n)$, with the floor $\widetilde{\deg}=\widetilde\Omega(\mathrm{D}^{1/4})=\widetilde\Omega(n^{1/4})$ [ABKRT21]. The recorded $\mathrm{Q}=\widetilde\Theta(n)$ is what makes this the $\mathrm{Q}$-vs-$\widetilde{\deg}$ separation. |
| \(\lambda(f)\) Spectral sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\lambda=O(\widetilde{\deg})$ [ABKRT21], with the floor $\lambda=\widetilde\Omega(\mathrm{D}^{1/6})$. ABKRT21 |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\widetilde\Theta(\sqrt n)\) | Upgraded to a two-sided bound: the upper bound below, plus $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Theta(n)$. The same uniqueness makes the $1$-certificates of $\mathrm{BKK}_{\mathrm{CS}}$ unambiguous, giving $\mathrm{Q}=\widetilde\Omega(\mathrm{UC}_{\min}^2)$ [BHT17, Cor. 2, attributed to AKK16]. This is the input to the \(f_{\mathrm{BHT}}\) amplification. BHT17 |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\widetilde\Theta(\sqrt n)\) putative | Upper: $\mathrm{C}^0\le\mathrm{C}=\widetilde O(\sqrt n)$. Lower: $\mathrm{D}\le\mathrm{C}^0\mathrm{C}^1\le\mathrm{C}^0\cdot\mathrm{C}$ with $\mathrm{D}=\widetilde\Theta(n)$ and $\mathrm{C}=\widetilde O(\sqrt n)$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(\widetilde\Theta(\sqrt n)\) putative | Same squeeze as the $\mathrm{C}^0$ line with the two sides exchanged; the $1$-certificates are moreover unambiguous, which is what the $\mathrm{UC}_{\min}$ line records. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{C}_{\min}\le\mathrm{C}=\widetilde O(\sqrt n)$. No matching lower bound is claimed -- a single cheaply certified input would not disturb anything above. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{fbs}$ and $\mathrm{C}$, which coincide at $\widetilde\Theta(\sqrt n)$. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a quadratic $\mathrm{Q}$-vs-$\mathrm{EC}$ gap. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{UC}\ge\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$. Only the $1$-side is known to be unambiguously certifiable at that cost, which is why $\mathrm{UC}_{\min}$ is pinned above but $\mathrm{UC}$ is not. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\widetilde\Omega(\sqrt n)\) | Squeeze: every subcube of a monochromatic partition is a certificate, so $\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(\widetilde\Theta(\sqrt n)\) | For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}=\widetilde\Theta(\sqrt n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)). |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$, both $\widetilde\Theta(n)$. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})=\widetilde\Theta(n)$. Unlike the positive adversary below, the multiplicative adversary does see the full hardness. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\widetilde O(\sqrt n)\) | The certificate-complexity barrier: $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\widetilde O(\sqrt n)$, while $\mathrm{Q}=\widetilde\Theta(n)$. So the positive-weight adversary is quadratically too weak to certify the quantum complexity of this function -- one of the cleanest total-function instances of that barrier, and the reason $\mathrm{Adv}^{\pm}$ rather than $\mathrm{Adv}$ appears in the row above. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\widetilde\Theta(n)\) putative | Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ gives $\mathrm{CG}=\widetilde\Omega(n)$, and $\mathrm{CG}\le\mathrm{C}^0\mathrm{C}^1=\widetilde O(n)$ gives the matching upper bound. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\widetilde\Theta(n)\) | For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Theta(n)$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\widetilde\Theta(n)\) | The distributional form of $\mathrm{R}$: $\overline{\mathrm{R}}=\Theta(\mathrm{R})=\widetilde\Theta(n)$. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(\widetilde O(\sqrt n)\) | Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(\sqrt n)$. Like $\widetilde{\deg}$, one-sided approximate degree misses the quantum hardness by a fourth power. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(\sqrt n)$. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{rdeg}\le\mathrm{C}=\widetilde O(\sqrt n)$. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde O(\sqrt n)$ (equally, $\mathrm{I}\le\deg$). Against $\mathrm{Q}=\widetilde\Theta(n)$ this gives $\mathrm{Q}=\widetilde\Omega(\mathrm{I}^2)$ for a total function. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(\widetilde O(\sqrt 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(\sqrt n)$. |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(\widetilde O(\sqrt n)\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}=\widetilde O(\sqrt n)$. OSSS ($\mathrm{D}\ge\mathrm{Var}/\mathrm{MaxInf}$) gives nothing here because $\mathrm{BKK}_{\mathrm{CS}}$ is essentially never satisfied under the uniform measure. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{s}^0\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$. Against $\mathrm{Q}=\widetilde\Theta(n)$ this alone is a quadratic $\mathrm{Q}$-vs-$\mathrm{s}^0$ gap. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{s}^1\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$. No floor is claimed for either side separately; Huang's $\mathrm{s}\ge\sqrt{\mathrm{bs}}$ only bounds the two-sided maximum. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{bs}^0\le\mathrm{bs}=\widetilde O(\sqrt n)$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{bs}^1\le\mathrm{bs}=\widetilde O(\sqrt n)$. Nisan's refined bound $\mathrm{C}^1\le\mathrm{s}^0\,\mathrm{bs}^1$ with $\mathrm{C}^1=\widetilde\Theta(\sqrt n)$ and $\mathrm{s}^0=\widetilde O(\sqrt n)$ gives only $\mathrm{bs}^1=\widetilde\Omega(1)$, so neither side of $\mathrm{bs}$ can be pinned from the recorded data. |
| \(\chi(f)\) Conflict complexity | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Floors: $\chi\ge\Omega(\mathrm{bs})=\widetilde\Omega(\sqrt n)$ [Li18], and $\mathrm{R}=O(\chi^2)$ [Sanyal18] with $\mathrm{R}=\widetilde\Theta(n)$ gives the same. Ceiling $\chi=O(\mathrm{R})=\widetilde O(n)$. Li18 Sanyal18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]: the floor is the $\mathrm{RS}$ floor $\widetilde\Omega(\sqrt n)$ and the ceiling is $\mathrm{R}=\widetilde O(n)$. GLSS19 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Squeezed between $\bar\chi$ and $\mathrm{R}$, neither of which is pinned here; also $\mathrm{LR}=\Omega(\sqrt{\mathrm{R}})=\widetilde\Omega(\sqrt n)$ directly. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\widetilde\Theta(n)\) | Unlike $\mathrm{LR}$ and $\bar\chi$, the quantum-aware relaxation is pinned: $\mathrm{R}^*\ge\Omega(\mathrm{Q})=\widetilde\Omega(n)$ and $\mathrm{R}^*\le\mathrm{R}=\widetilde O(n)$. So the cheat-sheet hardness is visible to $\mathrm{R}^*$ even though it may be invisible to the purely classical relaxations above. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$ with $\mathrm{R}=\widetilde\Theta(n)$; the noise overhead vanishes into the tilde. FRPU94 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05] with $\mathrm{Q}=\widetilde\Theta(n)$. BNRdW05 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\widetilde\Theta(\sqrt n)\) | The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$ for total functions [ABIKPS17]. Read against the recorded $\mathrm{CG}=\widetilde\Theta(n)$, this family is a quadratic separation of private-coin from public-coin certificate games -- private coins are the one escapee from the collapse $\mathrm{CG}^{\mathrm{ns}}=\mathrm{CG}^*=\mathrm{CG}^{\mathrm{pub}}=\Theta(\mathrm{CA})$. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\widetilde\Theta(\sqrt n)\) | Same collapse as the $\mathrm{CG}^{\mathrm{pub}}$ line: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\widetilde\Theta(\sqrt n)$. ABIKPS17 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\widetilde\Theta(\sqrt n)\) | Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$. ABIKPS17 |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n)$ [JainKlauck10, Thm 3.1]. Best floor available: $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(\sqrt n)$ (the $\widetilde{\deg}$ and $\mathrm{CA}$ floors are no better, and $\mathrm{D}=O(\mathrm{prt}_{1/3}^3)$ only gives $\widetilde\Omega(n^{1/3})$). Whether the partition bound sees cheat-sheet hardness is exactly this gap. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | The relaxation only loses from above, $\mathrm{rprt}\le\mathrm{prt}=\widetilde O(n)$, and every floor quoted on the $\mathrm{prt}$ line survives it, so the same range applies. JainKlauck10 |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n)$. The ceiling is the cheat-sheet input length $n^{10+o(1)}$, which is not comparable to the other entries in this scale. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}=\widetilde\Omega(n)$; the ceiling is again the input length $n^{10+o(1)}$ rather than anything in the $n$-scale. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{D}\le\mathrm{DTsize}-1$, so $\mathrm{DTsize}=\widetilde\Omega(n)$. The much stronger $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$ route is unavailable because $\mathrm{C}_{\min}$, and hence $\mathrm{rank}$, has no recorded floor here. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(\sqrt n)$. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a quadratic gap. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(\sqrt n)$. Nondeterministic quantum query complexity is quadratically below $\mathrm{Q}$ here. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{rdeg}_{1/3}\le\min\{\mathrm{rdeg},\widetilde{\deg}\}=\widetilde O(\sqrt n)$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a total function on which post-selection gives a quadratic speedup over bounded-error quantum queries. MahadevdeWolf15 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) | Ceiling: a depth-$\mathrm{D}$ decision tree is an exact conical junta of width $\mathrm{D}$ (one conjunction per accepting path, all coefficients $1$), so $\mathrm{cjdeg}\le\mathrm{D}=\widetilde O(n)$. Floor: $\mathrm{cjdeg}\ge\widetilde{\deg}=\widetilde\Omega(n^{1/4})$. Since $\mathrm{Q}=\widetilde\Theta(n)$, pinning this cell at the bottom of its range would give a $\mathrm{Q}$-vs-$\mathrm{cjdeg}$ separation strictly stronger than the recorded $\mathrm{Q}$-vs-$\widetilde{\deg}$ one. |
| \(\deg_2(f)\) Mod-2 degree | \(\widetilde O(\sqrt n)\) | The exact multilinear representation over $\mathbb{R}$ has integer coefficients (Moebius inversion of $f$), so reducing it mod $2$ represents $f$ over $\mathbb{F}_2$ and $\deg_2\le\deg=\widetilde O(\sqrt n)$. |
| \(\deg_p(f)\) Mod-p degree | \(\widetilde O(\sqrt n)\) | Same integrality argument as the $\deg_2$ line, for every prime $p$: $\deg_p\le\deg=\widetilde O(\sqrt n)$. |
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. 131 in total, strongest first.
-
\(\mathrm{Q}_{\varepsilon}(f_n) = \widetilde\Omega\big(\mathrm{QC}(f_n)^{4}\big)\)from \(\mathrm{Q}_{\varepsilon}(f) = \widetilde\Theta(n)\) against \(\mathrm{QC}(f) = \widetilde\Theta(n^{1/4})\)
-
\(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{2}\big)\)from \(\mathrm{D}(f) = \widetilde\Theta(n)\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = \widetilde\Omega\big(\deg(f_n)^{2}\big)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \widetilde\Theta(n)\) against \(\deg(f) = \widetilde O(\sqrt n)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) = \widetilde\Omega\big(\deg_p(f_n)^{2}\big)\)from \(\mathrm{R}_{\varepsilon}(f) = \widetilde\Theta(n)\) against \(\deg_p(f) = \widetilde O(\sqrt n)\)
-
\(\mathrm{R}^{*}(f_n) = \widetilde\Omega\big(\mathrm{C}(f_n)^{2}\big)\)from \(\mathrm{R}^{*}(f) = \widetilde\Theta(n)\) against \(\mathrm{C}(f) = \widetilde O(\sqrt n)\)
-
\(\mathrm{Q}_{0}(f_n) = \widetilde\Omega\big(\mathrm{bs}(f_n)^{2}\big)\)from \(\mathrm{Q}_{0}(f) = \widetilde\Theta(n)\) against \(\mathrm{bs}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{Q}^{\mathrm{rob}}(f_n) = \widetilde\Omega\big(\mathrm{fbs}(f_n)^{2}\big)\)from \(\mathrm{Q}^{\mathrm{rob}}(f) = \widetilde\Theta(n)\) against \(\mathrm{fbs}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{Adv}^{\pm}(f_n) = \widetilde\Omega\big(\mathrm{RC}(f_n)^{2}\big)\)from \(\mathrm{Adv}^{\pm}(f) = \widetilde\Theta(n)\) against \(\mathrm{RC}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\gamma_2^{\alpha}(f_n) = \widetilde\Omega\big(\mathrm{EC}(f_n)^{2}\big)\)from \(\gamma_2^{\alpha}(f) = \widetilde\Theta(n)\) against \(\mathrm{EC}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{MAdv}(f_n) = \widetilde\Omega\big(\mathrm{FC}(f_n)^{2}\big)\)from \(\mathrm{MAdv}(f) = \widetilde\Theta(n)\) against \(\mathrm{FC}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{Q}_{0}(f_n) = \widetilde\Omega\big(\mathrm{QC}(f_n)^{4}\big)\)from \(\mathrm{Q}_{0}(f) = \widetilde\Theta(n)\) against \(\mathrm{QC}(f) = \widetilde\Theta(n^{1/4})\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = \widetilde\Omega\big(\mathrm{UC}_{\min}(f_n)^{2}\big)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \widetilde\Theta(n)\) against \(\mathrm{UC}_{\min}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) = \widetilde\Omega\big(\deg(f_n)^{2}\big)\)from \(\mathrm{R}_{\varepsilon}(f) = \widetilde\Theta(n)\) against \(\deg(f) = \widetilde O(\sqrt n)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) = \widetilde\Omega\big(\deg_p(f_n)^{2}\big)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \widetilde\Theta(n)\) against \(\deg_p(f) = \widetilde O(\sqrt n)\)
… and 117 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{Q} = \widetilde\Omega(\widetilde{\deg}^4)$: approximate degree does not characterise quantum query complexity, even for total functions. Matches the upper bound $\mathrm{Q}\le\mathrm{D}=O(\widetilde{\deg}^4)$. Settled.
-
$\mathrm{Q}_E = \widetilde\Omega(\widetilde{\deg}^4)$.
-
$\mathrm{Q} = \widetilde\Omega(\mathrm{C}^2)$, matching $\mathrm{Q}\le\mathrm{D}\le\mathrm{C}^2$. Settled.
-
$\mathrm{Q} = \widetilde\Omega(\mathrm{bs}^2)$ against $\mathrm{Q}=O(\mathrm{bs}^3)$.
-
$\mathrm{Q} = \widetilde\Omega(\deg^2)$ against $\mathrm{Q}=O(\deg^3)$.
-
Applying the cheat-sheet transformation to $k$-Forrelation gives a total function with $\mathrm{R} = \widetilde\Omega(\mathrm{Q}^3)$; the upper bound is $\mathrm{R}\le\mathrm{D}=O(\mathrm{Q}^4)$, so this cell is still open in $[3,4]$.
Cited as a witness by
-
\(\mathrm{Q}(f_n) = \widetilde\Omega(\widetilde{\deg}(f_n)^4)\)
-
\(\mathrm{Q}(f_n) = \widetilde\Omega(\deg(f_n)^2)\)
-
\(\mathrm{Adv}^{\pm}(f_n) = \widetilde\Omega\big(\mathrm{Adv}(f_n)^2\big)\)
Notes
Cheat sheets are the single most productive device in this table: every partial-function speedup that comes with short certificates can be "totalised". They cost polylog factors, which is why so many cells carry $\widetilde\Omega$ rather than $\Omega$.
The values above describe one instantiation, $\mathrm{BKK}$ and
$\mathrm{BKK}_{\mathrm{CS}}$, which is the one that supplies the
$\mathrm{Q}$-vs-$\mathrm{C}$, $\mathrm{Q}$-vs-$\mathrm{bs}$,
$\mathrm{Q}$-vs-$\deg$ and $\mathrm{Q}$-vs-$\mathrm{UC}_{\min}$ gaps. Two
other instantiations appear in the witness list and are different
functions, so their numbers are deliberately not merged into the table:
- $\mathrm{R}=\widetilde\Omega(\mathrm{Q}^3)$ uses Forrelation composed with $\mathrm{AND}$-$\mathrm{OR}$ and then cheat-sheeted [ABK16, Thm 1]; the cubic exponent is now known to be the truth for $k$-Forrelation [BansalSinha21, SSW21].
- $\mathrm{Q}=\widetilde\Omega(\widetilde{\deg}^4)$ uses $\mathrm{RecBKK}_{\mathrm{CS}}$, $\mathrm{BKK}$ composed with itself $d=\Theta(\sqrt{\log n/\log\log n})$ times [ABK16, Thms 2, 13]. Its bounds are $\mathrm{Q}=n^{1-o(1)}$ and $\widetilde{\deg}=n^{1/4+o(1)}$, where the $o(1)$ hides a $\exp(\Theta(\sqrt{\log n\log\log n}))$ factor rather than a polylog -- too coarse to record as a $\widetilde O(\cdot)$ value.