Goos-Jayram-Pitassi-Watson function
Randomized analogue of GPW: $\mathrm{R}_0, \mathrm{R} = \widetilde\Omega(\deg^2)$.
total arity: $n$ bits
Description
The randomized-communication-vs-partition-number construction, read as a query-complexity function.
Formal definition
Tribes-List, $\mathrm{TL}$ [GJPW18, Sec. 3.1]. The input is a $k\times k$ matrix over $\Sigma = \{0,1\}\times([k]^{k-1}\cup\{\bot\})$: each cell carries a bit $m_{ij}$ and either $\bot$ or a list of $k-1$ row indices, one for every other column. Encoding a cell takes $\Theta(k\log k)$ bits, so $n = \Theta(k^3\log k)$. Again the function is defined by an unambiguous decision tree, of cost $\Theta(k\log k)$: guess a column $j$, check that all $k$ of its bits are $1$ and that some cell holds a list, read that list in full, and check that each of the $k-1$ cells it points to carries a $0$. So $\mathrm{TL}$ is the "unique all-$1$ column, certified against all others" function, and $\mathrm{UP}^{dt}(\mathrm{TL}) = \Theta(k\log k)$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\widetilde\Theta(n^{2/3})\) | Lower bound $\widetilde\Omega(k^2)=\widetilde\Omega(n^{2/3})$: [GJPW18, Lem. 8] proves it even against the weaker one-sided-approximate model, $\mathrm{coWAPP}^{dt}_{0.05}(\mathrm{TL})\ge\widetilde\Omega(\mathrm{UP}^{dt}(\mathrm{TL})^2)$. Upper bound from $\mathrm{R}\le\mathrm{D}=\widetilde O(n^{2/3})$. GJPW18 |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\widetilde\Theta(n^{2/3})\) | Squeezed between $\mathrm{R}$ and $\mathrm{D}$, both $\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\widetilde\Theta(n^{2/3})\) | Squeeze: $\mathrm{D}\ge\mathrm{R}=\widetilde\Omega(n^{2/3})$ and $\mathrm{D}\le\mathrm{UC}_{\min}^2=\widetilde O(n^{2/3})$ [BHT17]. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(\widetilde O(n^{1/3})\) | The unambiguous decision tree costs $\Theta(k\log k)=\widetilde O(n^{1/3})$, so $\mathrm{C}_1\le\mathrm{UC}_1=\widetilde O(n^{1/3})$. GJPW18 |
| \(\deg(f)\) Exact degree | \(\widetilde O(n^{1/3})\) | Sum the leaf indicators of the unambiguous decision tree: $\deg\le\mathrm{UC}_1=\widetilde O(n^{1/3})$. Against $\mathrm{R}=\widetilde\Omega(n^{2/3})$ this is the recorded $\mathrm{R}=\widetilde\Omega(\deg^2)$. GJPW18 |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\widetilde\Theta(n^{1/3})\) | Upper $\mathrm{UC}_{\min}\le\mathrm{UC}_1=\widetilde O(n^{1/3})$; lower from $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^{2/3})$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\widetilde\Theta(n^{2/3})\) putative | Upper: $\mathrm{C}_0\le\mathrm{D}=\widetilde O(n^{2/3})$. Lower: take a $0$-input with exactly one all-$1$ column $c$, whose list sits in the last cell of $c$ and has at least one target carrying $1$. Every other column is refuted by a single $0$ bit, but refuting $c$ itself forces the certificate to pin the whole column -- the $k-1$ earlier pointer fields as $\bot$ plus the list itself, $\Theta(k^2\log k)=\widetilde\Theta(n^{2/3})$ bits. Fixing another column entirely to $1$ (the cheap $\Theta(k)$-bit block that works for all other columns) is not available, since no other column is all-$1$ in this input. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\widetilde\Theta(n^{2/3})\) | Squeeze: $\mathrm{C}\ge\mathrm{C}_0$ and $\mathrm{C}\le\mathrm{D}$. As in \(f_{\mathrm{GPW}}\) the asymmetry is total: $\mathrm{C}_1=\widetilde O(n^{1/3})$ against a maximal $\mathrm{C}_0$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\widetilde\Theta(n^{2/3})\) | Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\widetilde\Theta(n^{2/3})\) | Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$. So the two-sided partition number is maximal here, which is why the $\mathrm{R}$-vs-$\mathrm{SP}$ witness has to be the AND-composed variant. |
| \(\mathrm{s}(f)\) Sensitivity | \(\widetilde\Theta(n^{1/3})\) putative | Lower: at a $1$-input with a unique witness column, all $k$ bits of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}_1=\widetilde O(n^{1/3})$; at a $0$-input a single flip must create a witness column, and per column only the unique missing $1$, the unique non-zero target, or the $O(\log k)$ bits of the list entry addressing it can do that, so $\mathrm{s}_0=O(k\log k)$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\widetilde\Theta(n^{1/3})\) putative | Lower $\mathrm{bs}\ge\mathrm{s}$. Upper: $\mathrm{bs}_1\le\mathrm{C}_1$, and disjoint sensitive blocks at a $0$-input inject into the $k$ columns. Together with $\mathrm{C}=\widetilde\Theta(n^{2/3})$ this makes $\mathrm{C}=\widetilde\Theta(\mathrm{s}\cdot\mathrm{bs})$, i.e. Nisan's bound is tight on this family. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\widetilde\Omega(n^{1/3})\) | From $\mathrm{C}=O(\mathrm{fbs}^2)$ [Tal13] against $\mathrm{C}=\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17 |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | The sabotage inequality is $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{R}=\widetilde\Theta(n^{2/3})$ is only the ceiling. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(n^{1/3})$; the alternative $\mathrm{R}=O(\mathrm{RS}^2\log\mathrm{RS})$ [Thm 32] gives the same $\widetilde\Omega(n^{1/3})$. Since no total function with $\mathrm{RS}=o(\mathrm{R})$ is known the truth is presumably $\widetilde\Theta(n^{2/3})$, but that is not a theorem. BenDavidKothari18 |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\widetilde\Theta(n^{2/3})\) | Squeeze: $\mathrm{R}\le\mathrm{R}^1\le\mathrm{D}$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\widetilde\Theta(n^{2/3})\) | Maximised over input distributions: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}=\Theta(\mathrm{R})$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\widetilde\Omega(n^{2/3})\) | Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\widetilde\Theta(n^{1/3})$; the ceiling is $\mathrm{Q}\le\mathrm{R}=\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\widetilde O(n^{1/3})\) | Squeeze: $\widetilde{\deg}\le\deg=\widetilde O(n^{1/3})$. Against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is also $\mathrm{R}=\widetilde\Omega(\widetilde{\deg}^2)$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}\le\deg$. |
| \(\lambda(f)\) Spectral sensitivity | \(\widetilde O(n^{1/3})\) | Squeeze: $\lambda=O(\widetilde{\deg})$ [ABKRT21]. ABKRT21 |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(\widetilde\Theta(n^{1/3})\) putative | Lower: at a $1$-input with a unique witness column all $k=\widetilde\Theta(n^{1/3})$ bits of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}^1=\widetilde O(n^{1/3})$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde\Theta(n^{1/3})$; the $\mathrm{s}$ line bounds it directly by $O(k\log k)$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(\widetilde\Theta(n^{1/3})\) putative | Squeezed between $\mathrm{s}_1=\widetilde\Omega(n^{1/3})$ and $\mathrm{C}^1=\widetilde O(n^{1/3})$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(\widetilde O(n^{1/3})\) | From the block-injection argument on the $\mathrm{bs}$ line: disjoint sensitive blocks at a $0$-input inject into the $k$ columns, so $\mathrm{bs}_0=O(k)$. Against $\mathrm{C}^0=\widetilde\Theta(n^{2/3})$ the $0$-side alone already realises the quadratic $\mathrm{C}$-vs-$\mathrm{bs}$ gap. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\widetilde\Theta(n^{1/3})\) putative | Upper: $\mathrm{C}_{\min}\le\mathrm{C}^1=\widetilde O(n^{1/3})$. Lower: certifying a $1$ requires the whole witness column and its list, $\widetilde\Omega(n^{1/3})$ bits, and every $0$-input costs at least that much too. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\widetilde\Omega(n^{1/3})\) | A Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=\widetilde\Omega(n^{1/3})$; the ceiling is $\mathrm{rank}\le\mathrm{D}=\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(n^{1/3})$; the ceiling is $\mathrm{EC}\le\mathrm{C}=\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\widetilde\Omega(n^{2/3})\) | Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(\widetilde\Theta(n^{1/3})\) | For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\widetilde\Theta(n^{1/3})$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)). |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(\widetilde O(n^{1/3})\) | Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(n^{1/3})$. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{rdeg}\le\deg=\widetilde O(n^{1/3})$ (take the denominator $q\equiv 1$). Against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic $\mathrm{R}$-vs-$\mathrm{rdeg}$ gap. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}=\widetilde\Omega(n^{1/6})$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11 |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\widetilde\Omega(n^{2/3})\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n^{2/3})$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\widetilde\Theta(n^{2/3})\) | For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Theta(n^{2/3})$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\widetilde\Theta(n^{2/3})\) | The distributional form of $\mathrm{R}$: $\overline{\mathrm{R}}=\Theta(\mathrm{R})=\widetilde\Theta(n^{2/3})$. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde\Theta(n^{1/3})$ (equally, $\mathrm{I}\le\deg$). Against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic $\mathrm{R}$-vs-$\mathrm{I}$ gap. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(\widetilde O(n^{1/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^{1/3})$. |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(\widetilde O(n^{1/3})\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}\le\mathrm{s}=\widetilde\Theta(n^{1/3})$; against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic gap. |
| \(\chi(f)\) Conflict complexity | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Two floors that agree: $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(n^{1/3})$ [Li18] and $\mathrm{R}=O(\chi^2)$ [Sanyal18] with $\mathrm{R}=\widetilde\Theta(n^{2/3})$. Ceiling $\chi=O(\mathrm{R})=\widetilde O(n^{2/3})$. Li18 Sanyal18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]; equivalently $\bar\chi=\Omega(\sqrt{\mathrm{R}})=\widetilde\Omega(n^{1/3})$. GLSS19 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Squeezed between $\bar\chi$ and $\mathrm{R}$; the direct floor $\mathrm{LR}=\Omega(\sqrt{\mathrm{R}})$ gives the same $\widetilde\Omega(n^{1/3})$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Squeezed between $\mathrm{LR}=\widetilde\Omega(n^{1/3})$ and $\mathrm{R}=\widetilde\Theta(n^{2/3})$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\widetilde\Omega(n^{1/6})$ is weaker. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Theta(n^{2/3})\) | Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$ with $\mathrm{R}=\widetilde\Theta(n^{2/3})$ pinned; the noise overhead vanishes into the tilde. FRPU94 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde\Omega(n^{1/6}),\ \widetilde O(n^{2/3})\) | 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^{1/3}),\ \widetilde O(n^{2/3})\) | The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(n^{1/3})$ for total functions [ABIKPS17]; the ceiling is $\mathrm{CG}^{\mathrm{pub}}\le\mathrm{C}=\widetilde\Theta(n^{2/3})$. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17 |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(n^{1/3})$; ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n^{2/3})$ [JainKlauck10, Thm 3.1]. Since $\mathrm{D}=O(\mathrm{prt}_{1/3}^3)$ also gives only $\widetilde\Omega(n^{2/9})$, the cell stays a genuine quadratic gap. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | The $\mathrm{RC}$ floor survives the relaxation and $\mathrm{rprt}\le\mathrm{prt}$, so the $\mathrm{prt}$ range carries over. JainKlauck10 |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\widetilde\Omega(n^{1/6}),\ \widetilde O(\sqrt n)\) | Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Theta(n^{1/3})$; ceiling the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\widetilde\Theta(n^{2/3})\cdot\widetilde O(n^{1/3})}=\widetilde O(\sqrt n)$. Ambainis02 |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\widetilde\Omega(n^{1/6})\) | Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\widetilde\Omega(n^{1/6})$. LMRSS11 |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\widetilde\Omega(n^{1/3})}\) | A decision tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$ and the recorded $\mathrm{rank}=\widetilde\Omega(n^{1/3})$ gives an exponential size floor. The ceiling is the trivial $2^{\mathrm{D}}=2^{\widetilde O(n^{2/3})}$. EhrenfeuchtHaussler89 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(n^{1/3})$, both bounds coming from the unambiguous $1$-certificates. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(n^{1/3})$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{rdeg}_{1/3}\le\min\{\mathrm{rdeg},\widetilde{\deg}\}=\widetilde O(n^{1/3})$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line; against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic $\mathrm{R}$-vs-$\mathrm{PostQ}$ gap. MahadevdeWolf15 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\widetilde\Omega(n^{1/6}),\ \widetilde O(n^{2/3})\) | Floor $\mathrm{cjdeg}\ge\widetilde{\deg}\ge\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{1/6})$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\widetilde\Theta(n^{2/3})$. |
| \(\deg_2(f)\) Mod-2 degree | \(\widetilde O(n^{1/3})\) | The exact multilinear representation over $\mathbb{R}$ has integer coefficients, so reducing mod $2$ gives $\deg_2\le\deg=\widetilde O(n^{1/3})$. |
| \(\deg_p(f)\) Mod-p degree | \(\widetilde O(n^{1/3})\) | Same integrality argument as the $\deg_2$ line, for every prime $p$. |
Separations it witnesses
-
$\mathrm{R}_0 = \widetilde\Omega(\deg^2)$ against $\mathrm{R}_0 = O(\deg^3)$.
-
$\mathrm{R} = \widetilde\Omega(\deg^2)$ against $\mathrm{R} = O(\deg^3)$.
-
$\mathrm{R} = \widetilde\Omega(\mathrm{SP}^{1.5})$, from the AND-composed variant $\mathrm{AND}_q\circ\mathrm{TL}^q$ with $q = \mathrm{UC}_1(\mathrm{TL})$ [GJPW18, Lem. 9]; not from the values recorded here.
Notes
$\mathrm{TL}$ is \(f_{\mathrm{GPW}}\) made randomized-hard: replacing the GPW single pointer by a full list of $k-1$ pointers means that a randomized algorithm which has guessed the right column still cannot cheaply refute the other columns, which is what [GJPW18, Lem. 8] exploits. The price is a cell of $\Theta(k\log k)$ bits instead of $\Theta(\log k)$, which is why the exponents here read $2/3$ and $1/3$ in the input length rather than $1$ and $1/2$.
The $\mathrm{R}$-vs-$\mathrm{SP}$ witness is the AND-composed function $\mathrm{AND}_q\circ\mathrm{TL}^q$, a different function, so its numbers are not merged into the table above.