Pointer functions
The construction that refuted the Saks-Wigderson conjecture and set most of the top-left corner of the matrix.
total
arity: $n$ bits (a grid of cells, each holding a value plus pointers)— also: the ABB+17 functions, Goos-Pitassi-Watson-style pointer gadgets
Description
The input is an $m\times m$ grid of cells. Each cell holds a bit and a pointer to another cell. The function asks whether there is a column all of whose cells are marked, together with a pointer chain certifying it; the pointers let a randomized algorithm follow a short path to the answer, while a deterministic algorithm can be forced to explore much more of the grid. Several variants of the payload/pointer structure give different separations.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\widetilde\Omega(n)\) | On a $p\times m$ grid of cells the adversary of [ABBLSS17, Thm 2] leaves the value undetermined after $pm-1$ cell queries, and one cell costs $\lceil\log|\Sigma|\rceil=\Theta(\log n)$ bits, so $\mathrm{D}$ is the input length up to logarithms. This holds for every variant listed below, which is what makes the upper bounds in this table mutually comparable: each $\widetilde O(\cdot)$ entry below is measured on a variant whose $\mathrm{D}$ is still $\widetilde\Omega(n)$. ABBLSS17 |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\widetilde O(\sqrt n)\) | Variant $f_{2m,m}$ [ABBLSS17, Thm 4, Cor. 7]: $\widetilde O(m)$ cell queries on a grid of $2m^2$ cells, i.e. $\widetilde O(\sqrt n)$ bit queries. The back pointers let the Las Vegas algorithm halve the number of candidate zeroes each round. ABBLSS17 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\widetilde O(\sqrt n)\) | Variant $g_{m,m}$ [ABBLSS17, Thm 12, Cor. 14], for which $\mathrm{R}_0 = \widetilde\Omega(n)$ -- this is the $\mathrm{R}_0$-vs-$\mathrm{R}$ separation, so the two $\widetilde O(\sqrt n)$ lines here are attained on different variants. Proved there for one-sided error, which dominates $\mathrm{R}$. ABBLSS17 |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\widetilde O(\sqrt n)\) | Same variant $g_{m,m}$ [ABBLSS17, Thm 12, Cor. 14]: the exact quantum algorithm costs $\widetilde O(m)$ on $m^2$ cells. Since that variant has $\mathrm{R}_0=\widetilde\Omega(n)$ this is a quadratic $\mathrm{R}_0$-vs-$\mathrm{Q}_E$ gap, and against $\mathrm{D}=\widetilde\Omega(n)$ it gives $\mathrm{D}=\widetilde\Omega(\mathrm{Q}_E^2)$. ABBLSS17 |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$ [ABBLSS17, Thm 5, Cor. 7]: Grover search over columns costs $\widetilde O(\sqrt m)=\widetilde O(n^{1/4})$. ABBLSS17 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$ [ABBLSS17, Thm 22, Cor. 23]. The approximating polynomial is the sum over the $m$ candidate marked columns of the acceptance polynomials of a $\widetilde O(\sqrt m)$-query column verifier; the sum is legitimate because at most one column can be marked. ABBLSS17 |
| \(\lambda(f)\) Spectral sensitivity | \(\widetilde O(n^{1/4})\) | Squeeze: $\lambda(f)=O(\widetilde{\deg}(f))$ [ABKRT21, Thms 17-18] applied to the line above. This is where the $\mathrm{D}=\widetilde\Omega(\lambda^4)$ entry of the $\lambda$ column comes from. ABKRT21 |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\widetilde\Theta(n)\) | Squeezed between $\mathrm{D}=\widetilde\Omega(n)$ and the input length $n$. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$. Upper: a zero-error algorithm's transcript is a certificate, so $\mathrm{C}\le 2\,\mathrm{R}_0=\widetilde O(\sqrt n)$. Lower: $\mathrm{D}\le\mathrm{C}^2$ against $\mathrm{D}=\widetilde\Omega(n)$. So the $\mathrm{D}$-vs-$\mathrm{R}_0$ separation is simultaneously an extremal $\mathrm{D}=\widetilde\Theta(\mathrm{C}^2)$ family. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$. Upper $\mathrm{bs}\le\mathrm{C}$; lower $\mathrm{bs}\ge\mathrm{D}/\mathrm{C}=\widetilde\Omega(\sqrt n)$ from $\mathrm{D}\le\mathrm{C}\cdot\mathrm{bs}$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, which coincide here. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17 |
| \(\mathrm{s}(f)\) Sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$ on variant $f_{2m,m}$; Huang gives the floor $\mathrm{s}\ge\sqrt{\mathrm{bs}}=\widetilde\Omega(n^{1/4})$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\widetilde\Theta(n^{1/4})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$, so the adversary bound is as small as the algorithm. Reichardt11 |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11 |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\widetilde O(\sqrt n)\) | Variant $g_{m,m}$: the algorithm of [ABBLSS17, Thm 12] is stated for one-sided error, which is what the recorded $\mathrm{R}$ line quotes. ABBLSS17 |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\widetilde O(\sqrt n)\) | Variant $g_{m,m}$: squeeze $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E=\widetilde O(\sqrt n)$. |
| \(\deg(f)\) Exact degree | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{D}=O(\deg^3)$ [Midrijanis04] against $\mathrm{D}=\widetilde\Omega(n)$. Exact degree cannot follow $\widetilde{\deg}=\widetilde O(n^{1/4})$ down. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$. 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}$, and $\mathrm{D}=\widetilde\Omega(n)$ with $\mathrm{C}=\widetilde O(\sqrt n)$ forces $\mathrm{C}^0=\widetilde\Omega(\sqrt n)$. So neither side of the certificate complexity can be the cheap one. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$; the argument of the $\mathrm{C}^0$ line with the roles of the two sides exchanged. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$, a $2m\times m$ grid with $n=\widetilde\Theta(m^2)$ bits. Upper: $\mathrm{C}_{\min}\le\mathrm{C}=\widetilde O(\sqrt n)$. Lower: certifying a $1$ requires exhibiting a whole marked column, i.e. all $2m$ cells of it; certifying a $0$ requires an unmarked cell in each of the $m$ columns. So $\mathrm{C}_x\ge m=\widetilde\Omega(\sqrt n)$ for every input $x$, not just the worst one. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\widetilde\Theta(\sqrt n)\) | Squeezed between $\mathrm{fbs}=\widetilde\Theta(\sqrt n)$ and $\mathrm{C}=\widetilde\Theta(\sqrt n)$ on variant $f_{2m,m}$, which coincide. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\widetilde\Omega(\sqrt n)\) | Variant $f_{2m,m}$: a Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{rank}\le\mathrm{D}=\widetilde O(n)$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\widetilde\Omega(\sqrt n)\) | Variant $f_{2m,m}$: $\mathrm{UC}\ge\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$. No matching upper bound is claimed -- an unambiguous cover of the pointer function is not known to be as cheap as an ordinary certificate. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\widetilde\Omega(\sqrt n)\) | Variant $f_{2m,m}$: every subcube of a monochromatic partition is a certificate, so $\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{D}=O(\mathrm{UC}_{\min}^2)$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n)$, which holds on every variant. BHT17 |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: for a Boolean function the solution function is forced and every input is critical, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}=\widetilde\Theta(\sqrt n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)). |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$: $\mathrm{MAdv}=\Theta(\mathrm{Q})$, so the multiplicative adversary is as small as the algorithm. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$: $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\widetilde O(n^{1/4})$. Note the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\widetilde O(\sqrt n)$ is the weaker of the two bounds here. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\widetilde O(\sqrt n)\) | Variant $g_{m,m}$: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde O(\sqrt n)$ by Yao's minimax. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\widetilde O(\sqrt n)\) | Variant $g_{m,m}$: the distributional/average-case form of $\mathrm{R}$, $\overline{\mathrm{R}}=\Theta(\mathrm{R})=\widetilde O(\sqrt n)$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\widetilde O(\sqrt n)\) | Variant $g_{m,m}$: for a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde O(\sqrt n)$. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{1/4})$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: $\mathrm{sdeg}\le\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{1/4})$. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(\widetilde O(\sqrt n)\) | Variant $f_{2m,m}$: $\mathrm{rdeg}\le\mathrm{C}=\widetilde O(\sqrt n)$ -- write the exact rational representation from the certificate cover. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: $\mathrm{I}(f)=O(\widetilde{\deg}(f))$ [Shi00] applied to $\widetilde{\deg}=\widetilde O(n^{1/4})$. Against $\mathrm{D}=\widetilde\Omega(n)$, valid on the same variant, this is a fourth-power $\mathrm{D}$-vs-$\mathrm{I}$ gap for a function whose sensitivity is still polynomially large. Shi00 |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(\widetilde O(n^{1/4})\) | 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^{1/4})$ on variant $\tilde h_{1,m,m}$. |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: a maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}=\widetilde O(n^{1/4})$. OSSS gives no useful floor here because the function is very unbalanced under the uniform measure, so $\mathrm{Var}=o(1)$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$, a $2m\times m$ grid with $n=\widetilde\Theta(m^2)$ bits. Lower: a $1$-input has one all-marked column, and it is unique, so flipping the marked bit of any one of that column's $2m$ cells leaves no all-marked column at all and sends the value to $0$. That is $2m=\widetilde\Omega(\sqrt n)$ sensitive coordinates at a single input. Upper: $\mathrm{s}^1\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$. Combined with the recorded $\mathrm{s}$ line this pins $\mathrm{s}=\widetilde\Theta(\sqrt n)$: the pointer function is not a sensitivity separation, and all of its gaps against $\mathrm{D}$ live on the randomized/quantum side. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{s}^0\le\mathrm{s}\le\mathrm{bs}=\widetilde O(\sqrt n)$ on variant $f_{2m,m}$. The $\mathrm{s}=\widetilde\Theta(\sqrt n)$ pin comes entirely from the $1$-side (see the $\mathrm{s}^1$ line), so no matching floor is claimed for $\mathrm{s}^0$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$. The $2m$ singleton blocks of the $\mathrm{s}^1$ line are pairwise disjoint and each is sensitive, so $\mathrm{bs}^1\ge\mathrm{s}^1=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{bs}^1\le\mathrm{bs}=\widetilde O(\sqrt n)$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{bs}^0\le\mathrm{bs}=\widetilde O(\sqrt n)$ on variant $f_{2m,m}$. Against $\mathrm{D}=\widetilde\Omega(n)$ this alone is a quadratic $\mathrm{D}$-vs-$\mathrm{bs}^0$ gap. No floor is claimed: the natural candidate blocks (mark a whole column) are $m$ disjoint blocks but their sensitivity depends on the pointer conventions of the variant. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$. Ceiling: $\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(\sqrt n)$. Floor: $\mathrm{fbs}\le\mathrm{CG}^{\mathrm{pub}}\le\mathrm{RS}$, and $\mathrm{fbs}=\widetilde\Theta(\sqrt n)$ here. So randomized sabotage is tight against $\mathrm{R}$ on this family, consistent with the fact that no total function with $\mathrm{RS}=o(\mathrm{R})$ is known. BenDavidKothari18 ABIKPS17 |
| \(\chi(f)\) Conflict complexity | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$. Floor $\chi\ge\Omega(\mathrm{bs})=\widetilde\Omega(\sqrt n)$ [Li18]; ceiling $\chi=O(\mathrm{R})=\widetilde O(\sqrt n)$, since $\mathrm{R}(f\circ g)=\Omega(\mathrm{R}(f)\chi(g))$ would otherwise beat $\mathrm{R}(f\circ g)=O(\mathrm{R}(f)\mathrm{R}(g))$. Li18 Sanyal18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: squeezed between $\mathrm{RS}=\widetilde\Theta(\sqrt n)$ and $\mathrm{R}=\widetilde O(\sqrt n)$ along the chain $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]. GLSS19 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: squeezed between $\bar\chi=\widetilde\Theta(\sqrt n)$ and $\mathrm{R}=\widetilde O(\sqrt n)$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: squeezed between $\mathrm{LR}=\widetilde\Theta(\sqrt n)$ and $\mathrm{R}=\widetilde O(\sqrt n)$. The quantum floor $\mathrm{R}^*\ge\Omega(\mathrm{Q})=\widetilde\Omega(n^{1/4})$ is weaker. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Theta(\sqrt n)\) | Variant $g_{m,m}$: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$, and $\mathrm{R}=\widetilde\Theta(\sqrt n)$ there ($\widetilde O(\sqrt n)$ by [ABBLSS17, Thm 12], $\widetilde\Omega(\sqrt n)$ from $\mathrm{fbs}$). The noise overhead is inside the tilde. FRPU94 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$: $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05] applied to $\mathrm{Q}=\widetilde O(n^{1/4})$. BNRdW05 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: the public-coin certificate game value collapses to $\Theta(\mathrm{CA})$, and $\mathrm{CA}=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$ for total functions [ABIKPS17]. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: $\mathrm{CG}^{\mathrm{ns}}$, $\mathrm{CG}^*$ and $\mathrm{CG}^{\mathrm{pub}}$ all collapse to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$. ABIKPS17 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: same collapse as the $\mathrm{CG}^{\mathrm{ns}}$ line -- entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$ here. ABIKPS17 |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Variant $f_{2m,m}$. The total-function sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0,\mathrm{CA}\}\le\mathrm{CG}\le\min\{\mathrm{C}^0\mathrm{C}^1,O(\mathrm{EC}^2)\}$ with $\mathrm{C}^0=\mathrm{C}^1=\mathrm{EC}=\widetilde\Theta(\sqrt n)$ gives the ceiling $\widetilde O(n)$; the floor is $\mathrm{R}_0$ on this variant, which is only $\widetilde\Omega(\sqrt n)$. Private coins are the one escapee from the collapse recorded in the three lines above, so the gap between this line and $\mathrm{CG}^{\mathrm{pub}}$ is genuine and open. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\widetilde\Theta(\sqrt n)\) | Variant $g_{m,m}$: $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(\sqrt n)$ [JainKlauck10, Thm 3.1], and $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(\sqrt n)$. So the partition bound is tight against $\mathrm{R}$ here and does not see the $\mathrm{D}$-vs-$\mathrm{R}$ gap. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\widetilde\Theta(\sqrt n)\) | Variant $g_{m,m}$: $\mathrm{rprt}\le\mathrm{prt}=\widetilde O(\sqrt n)$, and the $\mathrm{RC}$ floor survives the relaxation, so $\mathrm{rprt}=\widetilde\Omega(\sqrt n)$ too. JainKlauck10 |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Variant $f_{2m,m}$: $\mathrm{R}\le\mathrm{R}^{\mathrm{na}}\le\mathrm{D}^{\mathrm{na}}=\widetilde\Theta(n)$, with $\mathrm{R}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$. Nonadaptivity is expected to cost the full input length here, since the whole point of the pointer payload is that queries must chase a chain. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\widetilde\Omega(\sqrt n)}\) | Variant $f_{2m,m}$: a decision tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$, and $\mathrm{rank}\ge\mathrm{C}_{\min}=\widetilde\Omega(\sqrt n)$ from the Prover-Delayer game. The ceiling is the trivial $2^{\mathrm{D}}=2^{\widetilde O(n)}$. EhrenfeuchtHaussler89 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\widetilde O(\sqrt n)\) | Variant $f_{2m,m}$: $\mathrm{ndeg}\le\mathrm{C}^1=\widetilde\Theta(\sqrt n)$ -- sum the $1$-certificate indicator conjunctions, which are non-negative and cannot cancel. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\widetilde O(\sqrt n)\) | Variant $f_{2m,m}$: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil$, so the $\mathrm{ndeg}$ line transfers verbatim. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: $\mathrm{rdeg}_{1/3}\le\widetilde{\deg}=\widetilde O(n^{1/4})$ (a polynomial is a rational function with denominator $1$). |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line. Post-selection buys nothing beyond bounded-error quantum here. MahadevdeWolf15 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) | Variant $f_{2m,m}$: 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)$; the floor is $\mathrm{cjdeg}\ge\widetilde{\deg}\ge\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{1/4})$. |
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. 10 in total.
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\mathrm{N}_{p}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\widetilde\Omega(\sqrt n)}\) against \(\mathrm{N}_{p}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = \widetilde\Omega\big(\mathrm{Q}^{\mathrm{rob}}(f_n)^{4}\big)\)from \(\mathrm{D}^{\mathrm{na}}(f) = \widetilde\Theta(n)\) against \(\mathrm{Q}^{\mathrm{rob}}(f) = \widetilde O(n^{1/4})\)
-
\(\mathrm{C}_{\min}(f_n) = \widetilde\Omega\big(\mathrm{Q}_{\varepsilon}(f_n)^{2}\big)\)from \(\mathrm{C}_{\min}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{Q}_{\varepsilon}(f) = \widetilde O(n^{1/4})\)
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\overline{\mathrm{prt}}_{\varepsilon}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\widetilde\Omega(\sqrt n)}\) against \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \widetilde\Theta(\sqrt n)\)
-
\(\mathrm{C}_{\min}(f_n) = \widetilde\Omega\big(\mathrm{Q}^{\mathrm{rob}}(f_n)^{2}\big)\)from \(\mathrm{C}_{\min}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{Q}^{\mathrm{rob}}(f) = \widetilde O(n^{1/4})\)
-
\(\mathrm{C}_{\min}(f_n) = \widetilde\Omega\big(\mathrm{Adv}(f_n)^{2}\big)\)from \(\mathrm{C}_{\min}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{Adv}(f) = \widetilde O(n^{1/4})\)
-
\(\mathrm{C}_{\min}(f_n) = \widetilde\Omega\big(\mathrm{Adv}^{\pm}(f_n)^{2}\big)\)from \(\mathrm{C}_{\min}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{Adv}^{\pm}(f) = \widetilde O(n^{1/4})\)
-
\(\mathrm{C}_{\min}(f_n) = \widetilde\Omega\big(\gamma_2^{\alpha}(f_n)^{2}\big)\)from \(\mathrm{C}_{\min}(f) = \widetilde\Theta(\sqrt n)\) against \(\gamma_2^{\alpha}(f) = \widetilde O(n^{1/4})\)
-
\(\mathrm{C}_{\min}(f_n) = \widetilde\Omega\big(\mathrm{MAdv}(f_n)^{2}\big)\)from \(\mathrm{C}_{\min}(f) = \widetilde\Theta(\sqrt n)\) against \(\mathrm{MAdv}(f) = \widetilde O(n^{1/4})\)
-
\(\mathrm{C}_{\min}(f_n) = \widetilde\Omega\big(\widetilde{\deg}_{\varepsilon}(f_n)^{2}\big)\)from \(\mathrm{C}_{\min}(f) = \widetilde\Theta(\sqrt n)\) against \(\widetilde{\deg}_{\varepsilon}(f) = \widetilde O(n^{1/4})\)
Separations it witnesses
-
$\mathrm{D} = \widetilde\Omega(\mathrm{R}_0^2)$, and $\mathrm{D}=O(\mathrm{R}_0^2)$, so this cell is settled. Refutes the Saks-Wigderson conjecture ($\mathrm{D}=O(\mathrm{R}_0^{1.33})$).
-
$\mathrm{R}_0 = \widetilde\Omega(\mathrm{R}^2)$, matching $\mathrm{R}_0 = \widetilde O(\mathrm{R}^2)$. Settled.
-
$\mathrm{D}=\widetilde\Omega(\mathrm{R}^2)$ against the upper bound $\mathrm{D}\le 27\mathrm{R}^3$.
-
$\mathrm{D} = \widetilde\Omega(\mathrm{Q}^4)$, matching $\mathrm{D}=O(\mathrm{Q}^4)$. Settled.
-
$\mathrm{D} = \widetilde\Omega(\widetilde{\deg}^4)$, matching $\mathrm{D}=O(\widetilde{\deg}^4)$. Settled.
-
$\mathrm{R}_0 = \widetilde\Omega(\mathrm{Q}^3)$ against the upper bound $\mathrm{R}_0=O(\mathrm{Q}^4)$.
-
$\mathrm{R} = \widetilde\Omega(\mathrm{Q}_E^{3/2})$.
-
$\mathrm{D} = \widetilde\Omega(\lambda^4)$ against $\mathrm{D}=O(\lambda^6)$.
Cited as a witness by
-
\(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{R}(f_n)^2\big)\)
-
\(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{R}_0(f_n)^2\big)\)
-
\(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{R}^{1}(f_n)^2\big)\)
-
\(\mathrm{R}_0(f_n) = \widetilde\Omega\big(\mathrm{R}(f_n)^2\big)\)
-
\(\mathrm{D}(f_n) = \widetilde\Omega(\widetilde{\deg}(f_n)^4)\)
-
\(\mathrm{R}(f_n) = \widetilde\Omega(\widetilde{\deg}(f_n)^4)\)
-
\(\mathrm{D}(f_n) = \widetilde\Omega(\mathrm{Q}(f_n)^4)\)
-
\(\mathrm{D}(f_n) = \widetilde\Omega(\mathrm{Q}_E(f_n)^2)\)
Notes
The entry is a family of variants sharing one skeleton, and the values above mix them: each $\widetilde O(\cdot)$ line names the variant it is attained on. That is sound because $\mathrm{D}=\widetilde\Omega(n)$ holds for all of them, so every (lower, upper) pair the engine forms from this table is a statement about a single function. The variants are, in the notation of [ABBLSS17]: $f_{p,m}$ (a $p\times m$ grid, one distinguished all-ones column, back pointers), $g_{p,m}$ (adds a second pointer so that one-sided error and exact quantum algorithms get traction), and $h_{k,p,m}$ / $\tilde h_{k,p,m}$ (adds $k$ layers of pointers, tuned for approximate degree).