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

Goos-Pitassi-Watson partition-number function

The query-side function behind "deterministic communication vs partition number"; gives $\mathrm{D}=\widetilde\Omega(\deg^2)$.

total separating arity: $n$ bits

Description

A total function built to have small subcube-partition complexity but large deterministic complexity. Lifting it with a gadget yields the corresponding communication separation.

Formal definition

[GPW18, Thm 5]. The input is a $k\times k$ matrix over the alphabet $\Sigma = \{0,1\}\times([k]\times[k]\cup\{\bot\})$: each cell carries a bit and an optional pointer to another cell. The function is defined by an unambiguous decision tree of cost $2k-1$: guess a column, verify that all $k$ of its cells carry a $1$, follow the pointer stored in the first cell that has one, and check that the pointed-to cell carries a $0$. An adversary argument shows every deterministic tree needs $k^2$ cell queries. Encoding $\Sigma$ in $\lceil\log|\Sigma|\rceil = \Theta(\log k)$ bits gives a Boolean function on $n = \Theta(k^2\log k)$ bits and costs only that same logarithmic factor, hence $\mathrm{P}^{dt} \ge \widetilde\Omega(\mathrm{UP}^{dt\,2})$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(\widetilde\Theta(n)\) The adversary of [GPW18, Sec. 2.1] survives $k^2 = \widetilde\Theta(n)$ cell queries; and $\mathrm{D}\le n$ trivially. So this function is maximally hard deterministically, up to logarithms. GPW18
\(\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}^1(f)\) 1-certificate complexity \(\widetilde O(\sqrt n)\) The unambiguous decision tree above reads $2k-1 = \widetilde O(\sqrt n)$ cells, so $\mathrm{C}_1\le\mathrm{UC}_1\le\widetilde O(\sqrt n)$. GPW18
\(\deg(f)\) Exact degree \(\widetilde O(\sqrt n)\) Summing the indicator polynomials of the leaves of an unambiguous decision tree represents the function exactly, so $\deg\le\mathrm{UC}_1=\widetilde O(\sqrt n)$ [GPW18, Sec. 1.3]. Against $\mathrm{D}=\widetilde\Omega(n)$ this is the record $\mathrm{D}=\widetilde\Omega(\deg^2)$. GPW18
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\widetilde\Theta(\sqrt n)\) Upper $\mathrm{UC}_{\min}\le\mathrm{UC}_1=\widetilde O(\sqrt n)$; lower from $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n)$. The quadratic $\mathrm{D}$-vs-$\mathrm{UC}_{\min}$ gap is therefore optimal up to logarithms.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\widetilde\Theta(n)\) putative Upper: $\mathrm{C}_0\le\mathrm{D}=\widetilde O(n)$. Lower: take the $0$-input in which every matrix bit is $1$ and each column carries its single pointer in its last cell. A $0$-certificate must refute all $k$ columns; refuting column $j$ means either pinning its pointer chain (all $k$ cells of the column, since "the first cell that has a pointer" is only determined once the earlier cells are fixed to $\bot$) or ruling out $0$-valued targets globally, which means fixing all $k^2$ matrix bits to $1$. Both cost $\Theta(k^2)$ bits $=\widetilde\Theta(n)$.
\(\mathrm{C}(f)\) Certificate complexity \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\ge\mathrm{C}_0$ and $\mathrm{C}\le\mathrm{D}$. Note the asymmetry: $\mathrm{C}_1=\widetilde O(\sqrt n)$ but $\mathrm{C}_0$ is maximal.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$. It is the one-sided $\mathrm{UC}_1$ that is small here; the two-sided quantity is maximal, which is exactly why [GPW18] needs the AND-composed variant for the $\mathrm{SP}$ separation.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$.
\(\mathrm{s}(f)\) Sensitivity \(\widetilde\Theta(\sqrt n)\) putative Lower: at a $1$-input with a unique witness column, all $k$ cells of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}_1=\widetilde O(\sqrt n)$, and at a $0$-input a sensitive bit must single-handedly create a witness column, so it is either the target bit of one of the $k$ columns or one of the $O(\log k)$ pointer bits redirecting a column at an existing $0$, giving $\mathrm{s}_0=O(k\log k)$.
\(\mathrm{bs}(f)\) Block sensitivity \(\widetilde\Theta(\sqrt n)\) putative Lower $\mathrm{bs}\ge\mathrm{s}$. Upper: $\mathrm{bs}_1\le\mathrm{C}_1=\widetilde O(\sqrt n)$, and disjoint sensitive blocks at a $0$-input inject into the $k$ columns (two disjoint blocks cannot both complete the same column), so $\mathrm{bs}_0=O(k)$. Against $\mathrm{C}=\widetilde\Theta(n)$ this makes the function an extremal example for $\mathrm{C}=O(\mathrm{bs}^2)$ as well, alongside \(f_{\mathrm{GSS}}\).
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\widetilde\Omega(\sqrt n)\) From $\mathrm{C}=O(\mathrm{fbs}^2)$ [Tal13] against $\mathrm{C}=\widetilde\Theta(n)$. The block-injection argument recorded under $\mathrm{bs}$ suggests the matching $\widetilde O(\sqrt n)$, but the fractional relaxation is not covered by it.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{R}=\Omega(\mathrm{fbs})$. The gap up to $\mathrm{D}=\widetilde\Theta(n)$ is not closed here -- closing it in the other direction is precisely what \(f_{\mathrm{GJPW}}\) was built for.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$, and both ends are $\widetilde\Theta(n)$. A zero-error algorithm's transcript is a certificate, so the maximal $\mathrm{C}_0$ recorded above already pins $\mathrm{R}_0$ at the top even though $\mathrm{R}$ may be far smaller.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\widetilde\Theta(\sqrt n)$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\widetilde O(\sqrt n)\) Squeeze: $\widetilde{\deg}\le\deg=\widetilde O(\sqrt n)$.
\(\mathrm{sdeg}(f)\) Sign degree \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{sdeg}\le\widetilde{\deg}\le\deg$.
\(\lambda(f)\) Spectral sensitivity \(\widetilde O(\sqrt n)\) Squeeze: $\lambda=O(\widetilde{\deg})$ [ABKRT21]. Against $\mathrm{D}=\widetilde\Theta(n)$ this is another $\mathrm{D}=\widetilde\Omega(\lambda^2)$ family; the record is still the quartic one from \(g_{\mathrm{ABBLSS}}\). ABKRT21
\(\mathrm{s}^1(f)\) 1-sensitivity \(\widetilde\Theta(\sqrt n)\) putative Lower: at a $1$-input with a unique witness column all $k=\widetilde\Theta(\sqrt n)$ cells of that column are sensitive. Upper: $\mathrm{s}_1\le\mathrm{C}^1=\widetilde O(\sqrt n)$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{s}_0\le\mathrm{s}=\widetilde\Theta(\sqrt n)$; the $\mathrm{s}$ line above bounds it directly by $O(k\log k)$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\widetilde\Theta(\sqrt n)\) putative Squeezed between $\mathrm{s}_1=\widetilde\Omega(\sqrt n)$ and $\mathrm{C}^1=\widetilde O(\sqrt n)$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\widetilde O(\sqrt n)\) 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)=\widetilde O(\sqrt n)$. Combined with $\mathrm{C}^0=\widetilde\Theta(n)$ this is the extremal $\mathrm{C}^0=\widetilde\Omega(\mathrm{bs}_0^2)$ behaviour.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\widetilde\Theta(\sqrt n)\) putative Upper: $\mathrm{C}_{\min}\le\mathrm{C}^1=\widetilde O(\sqrt n)$. Lower: a $1$-certificate must exhibit all $k$ cells of a witness column plus the pointer check, so $\mathrm{C}_x=\widetilde\Omega(\sqrt n)$ at every $1$-input, and $0$-inputs cost $\widetilde\Theta(n)$.
\(\mathrm{rank}(f)\) Decision tree rank \(\widetilde\Omega(\sqrt n)\) 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\Theta(n)$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$ (equally, $\mathrm{R}_0=O(\mathrm{EC}^2)$ with $\mathrm{R}_0=\widetilde\Theta(n)$); the ceiling is $\mathrm{EC}\le\mathrm{C}=\widetilde\Theta(n)$.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\widetilde\Omega(n)\) Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\widetilde\Theta(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}=\mathrm{bs}=\widetilde\Theta(\sqrt n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\widetilde O(\sqrt n)\) Squeeze: $\widetilde{\deg}_+\le\widetilde{\deg}=\widetilde O(\sqrt n)$.
\(\mathrm{rdeg}(f)\) Rational degree \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{rdeg}\le\deg=\widetilde O(\sqrt n)$ (take the denominator $q\equiv 1$). Against $\mathrm{D}=\widetilde\Theta(n)$ this is a quadratic $\mathrm{D}$-vs-$\mathrm{rdeg}$ gap.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{Q}_E\ge\mathrm{Q}=\widetilde\Omega(n^{1/4})$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\widetilde\Theta(n)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{R}^1\ge\mathrm{R}=\widetilde\Omega(\sqrt n)$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) The sabotage inequality runs $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{R}$ is the ceiling: $\mathrm{RS}=O(\mathrm{R})\le O(\mathrm{D})=\widetilde O(n)$. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$. BenDavidKothari18
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{D}^{\mathrm{na}}=\widetilde\Theta(n)$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\widetilde\Omega(\sqrt n)\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Omega(\sqrt n)$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\widetilde\Omega(\sqrt n)\) The distributional form of $\mathrm{R}$: $\overline{\mathrm{R}}=\Theta(\mathrm{R})=\widetilde\Omega(\sqrt n)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\widetilde\Omega(\sqrt n)\) Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde\Omega(\sqrt n)$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde\Theta(\sqrt n)$ (equally, $\mathrm{I}\le\deg$). Against $\mathrm{D}=\widetilde\Theta(n)$ this gives a quadratic $\mathrm{D}$-vs-$\mathrm{I}$ gap.
\(\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}\le\mathrm{s}=\widetilde\Theta(\sqrt n)$. Against $\mathrm{D}=\widetilde\Theta(n)$ this is a quadratic gap.
\(\chi(f)\) Conflict complexity \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Floor $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(\sqrt n)$ [Li18]; ceiling $\chi=O(\mathrm{R})=\widetilde O(n)$. Li18
\(\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] between $\mathrm{RS}=\widetilde\Omega(\sqrt n)$ and $\mathrm{R}=\widetilde O(n)$. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Squeezed between $\bar\chi=\widetilde\Omega(\sqrt n)$ and $\mathrm{R}=\widetilde O(n)$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Squeezed between $\mathrm{LR}=\widetilde\Omega(\sqrt n)$ and $\mathrm{R}=\widetilde O(n)$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\widetilde\Omega(n^{1/4})$ is weaker.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Squeeze: $\mathrm{R}\le\mathrm{N}_p=O(\mathrm{R}\log\mathrm{R})$, so the noisy model inherits the whole $\mathrm{R}$ range. FRPU94
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range $[\widetilde\Omega(n^{1/4}),\widetilde O(n)]$. BNRdW05
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Omega(\sqrt n)$ for total functions [ABIKPS17]; the ceiling is $\mathrm{CG}^{\mathrm{pub}}\le\mathrm{C}=\widetilde\Theta(n)$. Against the recorded $\mathrm{CG}=\widetilde\Omega(n)$ this is where a private-coin/public-coin gap could appear. ABIKPS17
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(\sqrt n)$; ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n)$ [JainKlauck10, Thm 3.1]. At zero error the story is different: $\mathrm{prt}_0\ge\mathrm{C}=\widetilde\Theta(n)$. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) 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/4}),\ \widetilde O(n^{3/4})\) Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\widetilde\Theta(\sqrt n)$; ceiling the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\widetilde\Theta(n)\cdot\widetilde O(\sqrt n)}=\widetilde O(n^{3/4})$. Ambainis02
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\widetilde\Omega(n^{1/4})\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\widetilde\Omega(n^{1/4})$. LMRSS11
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\widetilde\Omega(\sqrt n)}\) 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(\sqrt n)$ gives an exponential size floor. The ceiling is the trivial $2^{\mathrm{D}}=2^{\widetilde O(n)}$. EhrenfeuchtHaussler89
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(\sqrt n)$; both bounds trace back to the same unambiguous $1$-certificates.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(\sqrt n)$.
\(\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, giving a quadratic $\mathrm{D}$-vs-$\mathrm{PostQ}$ gap. MahadevdeWolf15
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) Floor $\mathrm{cjdeg}\ge\widetilde{\deg}\ge\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{1/4})$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\widetilde\Theta(n)$.
\(\deg_2(f)\) Mod-2 degree \(\widetilde O(\sqrt n)\) The exact multilinear representation over $\mathbb{R}$ has integer coefficients, so reducing mod $2$ gives $\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$.

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. 1 in total.

Separations it witnesses

Cited as a witness by

Notes

Two functions live here. The values above are for the [GPW18, Thm 5] function, whose gap is against the one-sided unambiguous width $\mathrm{UC}_1$ (their $\mathrm{UP}^{dt}$). That one-sided quantity does not upper bound $\mathrm{SP}$, since an unambiguous DNF partitions only the $1$-inputs.

For the two-sided quantity one needs [GPW18, Thm 4]: with $g$ the function above and $q := \mathrm{UC}_1(g)$, the composition $f := \mathrm{AND}_q\circ g$ satisfies $\mathrm{UC}(f)=\widetilde O(q^2)$ (certify the $q$ copies one-sidedly and pay $\mathrm{D}(g)$ on the single exceptional copy) while $\mathrm{D}$ multiplies to $\widetilde\Omega(q^3)$. Since $\mathrm{SP}\le\mathrm{UC}$, this gives $\mathrm{D}=\widetilde\Omega(\mathrm{SP}^{1.5})$, matching the earlier bound of [KRS15]. It is the communication versions that reach the quadratic gap against the partition number [GPW18, Thm 2].