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

Goos-Jayram-Pitassi-Watson function

Randomized analogue of GPW: $\mathrm{R}_0, \mathrm{R} = \widetilde\Omega(\deg^2)$.

total separating 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

MeasureValueNotes
\(\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

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.