Ambainis-Belovs function
Constant exact degree ($\le 9$) against $\mathrm{Q} = \Omega(n^{1/3})$: the polynomial method is exponentially lossy off-promise.
partial
quantum
arity: $3n$ variables over an alphabet $[q]$ with $q \ge n^{12}$ (so $\Theta(n\log n)$ bits after binary encoding)— also: threshold satisfiability, tripartite shift problem
Description
Threshold satisfiability. Fix a system of $n^3$ "tripartite" linear equations over $\mathbb{Z}_q$, one for each triple of variables taken from three disjoint blocks $A, B, C$ of size $n$. Given an assignment, distinguish "no equation is satisfied" from "exactly $n$ equations are satisfied".
A counting argument picks right-hand sides for which no assignment ever satisfies as many as $4n$ equations. The number of satisfied equations is then a degree-$3$ polynomial taking values in $[0, 4n)$, and squashing it through a fixed univariate cubic that sends $0 \mapsto 0$, $1 \mapsto 1$ and keeps $[0,4]$ inside $[0,1]$ represents the function exactly in degree $9$. The quantum lower bound is a negative-weight adversary bound, and it has to be: the positive adversary is at most quadratic in the degree even for partial functions, so it could never prove more than $O(1)$ here.
Formal definition
Variables $x_1,\dots,x_{3n} \in \mathbb{Z}_q$; index blocks $A = \{1,\dots,n\}$, $B = \{n+1,\dots,2n\}$, $C = \{2n+1,\dots,3n\}$; fixed right-hand sides $r_{a,b,c} \in \mathbb{Z}_q$. Write $$K(x) \;=\; \#\{(a,b,c) \in A\times B\times C \;:\; x_a + x_b + x_c = r_{a,b,c}\}.$$ Then $f(x) = 0$ if $K(x) = 0$, $f(x) = 1$ if $K(x) = n$, and $f$ is undefined otherwise. The $r_{a,b,c}$ are called good when $K(x) < 4n$ for every $x$; for $q \ge n^{12}$ a good choice exists by the probabilistic method.
The lower bound is proved for the harder-to-satisfy tripartite shift restriction, in which the positive inputs are those whose set of satisfied equations is exactly a shifted tripartite matching $\mu_{s,t} = \{(j,\, n+1+(j+s \bmod n),\, 2n+1+(j+t \bmod n)) : j \in [n]\}$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\deg(f)\) Exact degree | \(9\) | Theorem 6, and the whole content of the upper bound. $K(x) = \sum_{a,b,c}\sum_{s,t} \mathbb{1}[x_a{=}s]\,\mathbb{1}[x_b{=}t]\,\mathbb{1}[x_c{=}r_{a,b,c}-s-t]$ has degree $3$ in the indicator variables $\mathbb{1}[x_i = v]$, and $T(z) = \tfrac14 z^3 - \tfrac32 z^2 + \tfrac94 z$ satisfies $T(0)=0$, $T(1)=1$ and $0 \le T \le 1$ on $[0,4]$, so $T(K(x)/n)$ represents $f$ exactly and is bounded on the whole cube. Degree $3 \times 3 = 9$, independent of $n$. AmbainisBelovs23 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(O(1)\) | At most $\deg \le 9$: an exactly representing polynomial is in particular an approximating one. So the separation below is simultaneously a $\mathrm{Q}$-vs-$\widetilde{\deg}$ separation, and that is the form in which it is usually quoted. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Omega(n^{1/3})\) | Theorem 1, via Theorem 8: the tripartite shift problem already needs $\Omega(n^{1/3})$ quantum queries whenever $q \ge 4n^3$, for every choice of right-hand sides. No matching upper bound is claimed; the construction is closely related to an earlier problem of Belovs and Rosmanis, whose lower bound it strengthens. AmbainisBelovs23 |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Omega(n^{1/3})\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, and here the negative-weight adversary is literally how the lower bound is obtained -- an explicit adversary matrix built from the shifted matchings. AmbainisBelovs23 |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(1)\)· putative | The positive-weight adversary is at most quadratic in the exact degree even for partial functions (Anshu, Ben-David and Kundu), so $\mathrm{Adv} = O(\deg^2) = O(1)$ while $\mathrm{Q} = \Omega(n^{1/3})$. This is exactly why the paper cannot use the positive adversary, and it makes the function a second \(\mathrm{Adv}(f)\)-vs-\(\mathrm{Q}_{\varepsilon}(f)\) witness alongside \(\mathrm{SIMON}_n\) and \(\mathrm{COL}_n\). |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Omega(n^{1/3})\) | Sandwiched from below: $\mathrm{MAdv} \ge \mathrm{Adv}^{\pm} = \Omega(n^{1/3})$. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Omega(n^{1/3})\) | $\gamma_2 = \Theta(\mathrm{Q}) = \Omega(n^{1/3})$. |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(O(n)\) | Reading all $3n$ variables determines the answer; no matching lower bound is proved, only $\mathrm{D} \ge \mathrm{Q} = \Omega(n^{1/3})$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(O(n)\) | The same $3n$ positions, fixed in advance. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Omega(n^{1/3})\) | Sandwiched: $\mathrm{Q} \le \mathrm{R} \le \mathrm{D}$, i.e. between $\Omega(n^{1/3})$ and $O(n)$. The paper says nothing more about the classical side. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Omega(n^{1/3})\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{sdeg}(f)\) Sign degree | \(O(1)\) | $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} \le \deg \le 9$. Everything in the degree column is a constant here; that is the point of the construction. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(O(1)\) | Between $\mathrm{sdeg}$ and $\widetilde{\deg} \le 9$. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(O(1)\) | Take $p$ to be the degree-$9$ exact representation and $q = 1$: a rational representation of degree $9$. So $\mathrm{rdeg} \le \deg \le 9$ while $\mathrm{Q} = \Omega(n^{1/3})$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(1)\) | $\mathrm{rdeg}_{\varepsilon} \le \mathrm{rdeg} = O(1)$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(1)\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(1)$ against $\mathrm{Q} = \Omega(n^{1/3})$. Post-selection is not the resource being separated -- rather, every polynomial-flavoured measure is blind to this function, which is precisely the failure of the polynomial method that [AmbainisBelovs23] exhibits. MahadevdeWolf15 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(O(1)\) | The exact representation $T(K(x)/n)$ is nonzero exactly on the $1$-inputs of the domain, so $\mathrm{ndeg} \le \deg \le 9$. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(O(1)\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil \le 5$. |
| \(\lambda(f)\) Spectral sensitivity | \(O(1)\) | $\lambda \le \mathrm{Adv} = O(\deg^2) = O(1)$. Spectral sensitivity, like every other measure bounded by the positive adversary, cannot see the $\Omega(n^{1/3})$ lower bound. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Omega(n^{1/3})\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D}$, i.e. between $\Omega(n^{1/3})$ and $O(n)$. Note that $\deg \le 2\mathrm{Q}_{\mathrm{E}}$ is useless in this direction -- $\deg$ is $9$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Omega(n^{1/3})\) | Between $\mathrm{Q} = \Omega(n^{1/3})$ and $\mathrm{Q}_{\mathrm{E}} = O(n)$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Omega(n^{1/3})\) | Between $\mathrm{R} = \Omega(n^{1/3})$ and $\mathrm{D} = O(n)$. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Omega(n^{1/3})\) | Between $\mathrm{R} = \Omega(n^{1/3})$ and $\mathrm{R}_0 = O(n)$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Omega(n^{1/3})\) | Between $\mathrm{R} = \Omega(n^{1/3})$ and $\mathrm{D}^{\mathrm{na}} = O(n)$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Omega(n^{1/3})\) | By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Omega(n^{1/3})$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Omega(n^{1/3})\) | $\mathrm{R}^* \ge \Omega(\mathrm{Q}) = \Omega(n^{1/3})$, since quantum query complexity composes perfectly -- a chain that, unlike $\mathrm{R}^* = \Omega(\mathrm{LR})$, is available for partial functions. |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Omega(n^{1/3})\) | Robust queries are at least as expensive as exact ones: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(n^{1/3})$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(\Omega(n^{2/3})\) | $\mathrm{Q}_{2/5}(f) = O(\sqrt{\mathrm{DTsize}(f)})$, so $\mathrm{DTsize} = \Omega(\mathrm{Q}^2) = \Omega(n^{2/3})$. This is one of the few places where a degree-blind lower bound propagates: the tree-size bound goes through $\mathrm{Q}$, not through $\deg$. |
| \(\mathrm{C}(f)\) Certificate complexity | \(O(n)\) | Reading all $3n$ variables is a certificate for either side. Nothing smaller is proved, and note that certificate complexity is not a lower-bound technique that could reach $\Omega(n^{1/3})$ anyway: $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1}$ is already known to be $O(1)$ here. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(O(n)\) | At most $\mathrm{C} = O(n)$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(O(n)\) | At most $\mathrm{C} = O(n)$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(O(1)\) | $\mathrm{bs} \le \mathrm{Adv}^2 = O(1)$ -- a chain that holds for partial functions, because each $x^{B_j}$ in Ambainis' argument is a domain point by definition of a sensitive block. So block sensitivity is blind to the $\Omega(n^{1/3})$ lower bound, as is everything below it. Ambainis02 |
| \(\mathrm{s}(f)\) Sensitivity | \(O(1)\) | $\mathrm{s} \le \mathrm{bs} = O(1)$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(O(1)\) | Both sides are capped: $\mathrm{Adv} = \Omega(\sqrt{\mathrm{bs}^0\,\mathrm{bs}^1})$ and $\mathrm{bs}^0, \mathrm{bs}^1 \le \mathrm{bs} = O(1)$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(O(1)\) | At most $\mathrm{bs} = O(1)$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(O(1)\) | At most $\mathrm{bs}^0 = O(1)$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(O(1)\) | At most $\mathrm{bs}^1 = O(1)$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Omega(n^{1/3})\) | Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Omega(n^{1/3})$, with $\mathrm{psD} \le \mathrm{D} = O(n)$ above. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(O(1)\) | Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = O(1)$. So the measure is as blind to this function as block sensitivity is. GoosPitassi14 |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(O(n)\) | At most $\mathrm{C} = O(n)$. The total-function shortcut $\mathrm{fbs} = \Theta(\mathrm{CA})$ [ABIKPS17] is unavailable on a promise, and the bound $\mathrm{fbs} = O(\widetilde{\deg}^2)$ is recorded only for total $f$, so nothing pins this to $O(1)$ even though $\mathrm{bs} = O(1)$. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(O(n)\) | Equal to $\mathrm{fbs}$ by LP duality. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(O(n)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = O(n)$. Aaronson06 |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(O(\sqrt n)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = O(\sqrt n)$. The other ceiling, $\mathrm{QC} \le \mathrm{Q}$, is useless here because only a lower bound on $\mathrm{Q}$ is known. Aaronson06 |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(O(n)\) putative | Exhibited directly, since $\mathrm{EC} \le \mathrm{C}$ needs a total function. Put $w^x_i = 1$ at every input and each of the $3n$ variables: any two inputs of different value differ somewhere, so $\sum_{i : x_i \ne y_i} w^x_i w^y_i \ge 1$, at cost $3n$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(O(n)\) | $\mathrm{CA} \le \mathrm{R} \le \mathrm{D} = O(n)$. From below only $\mathrm{CA} = \Omega(\mathrm{fbs}) = \Omega(1)$, so this is not pinned. Note $\mathrm{CA} = \Theta(\mathrm{fbs})$ is a total-function theorem and must not be used here. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(O(n)\) | $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = O(n)$ -- the LP-duality collapse survives a promise. Directly: on a shared random one of the $3n$ positions the players win with probability $\ge 1/(3n)$. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(O(n)\) | Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(O(n)\) | Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23 |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(O(n^2)\) putative | Private coins: both players output a uniformly random one of the $3n$ positions, winning with probability $\ge 1/(3n)^2$. The 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)\}$ is a total-function statement and is not used here. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(O(n)\) | At most $\mathrm{C} = O(n)$, i.e. $\min\{\mathrm{C}^0,\mathrm{C}^1\} \le O(n)$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(O(n)\) | At most $\mathrm{D} = O(n)$; equal to $\mathrm{SP}$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(O(n)\) | Equal to $\mathrm{UC}$, and at most $\mathrm{D} = O(n)$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(O(n)\) | At most $\mathrm{UC} = O(n)$. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(O(n)\) | At most $\mathrm{D} = O(n)$. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Omega(n^{1/6})\) | $\bar\chi = \Omega(\sqrt{\mathrm{R}})$ holds for partial $g$ as well, and $\mathrm{R} = \Omega(n^{1/3})$. Above, $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Omega(n^{1/6})\) | $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}}) = \Omega(n^{1/6})$, with $\mathrm{LR} \le \mathrm{R} = O(n)$ above. BBGM22 |
| \(\chi(f)\) Conflict complexity | \(O(n)\) | $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(O(n)\) | From $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R}) = O(n)$. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(O(n)\) | Sandwiched between $\widetilde{\deg} = O(1)$ and $\mathrm{R} = O(n)$; nothing pins it, which is the point -- conflict-degree tracks $\mathrm{R}$, not $\widetilde{\deg}$, and this function separates the two. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(O(n)\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(n)$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(O(n)\) | From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon = O(n)$. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(O(n)\) | At most $\mathrm{R} = O(n)$. The shortcut $\mathrm{R} = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$ is unavailable: only $\mathrm{R} = \Omega(n^{1/3})$ is known. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Omega(n^{1/3})\) | At least $\mathrm{R}$: setting the noise rate to $0$ recovers the ordinary model. Above, $\mathrm{N}_p = O(\mathrm{R}\log\mathrm{R}) = \widetilde O(n)$. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(O(n)\) | At most $\mathrm{R} = O(n)$. Unlike \(\mathrm{forr}\) the promise does not force $\mathrm{D}^{\mathrm{prod}} = 0$: two inputs of opposite value can differ in a single variable, so a rectangle inside the promise can meet both sides. |
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. 137 in total, strongest first.
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Omega(n^{2/3})\) against \(\mathrm{s}(f) = O(1)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \lambda(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Omega(n^{1/3})\) against \(\lambda(f) = O(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \deg(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Omega(n^{1/3})\) against \(\deg(f) = 9\)
-
\(\mathrm{R}_{0}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{R}_{0}(f) = \Omega(n^{1/3})\) against \(\mathrm{s}^0(f) = O(1)\)
-
\(\mathrm{R}^{*}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{R}^{*}(f) = \Omega(n^{1/3})\) against \(\mathrm{s}^1(f) = O(1)\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \Omega(n^{1/3})\) against \(\mathrm{rdeg}(f) = O(1)\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}(f_n) = O(1)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Omega(n^{1/3})\) against \(\mathrm{bs}(f) = O(1)\)
-
\(\mathrm{Q}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{Q}_{\varepsilon}(f) = \Omega(n^{1/3})\) against \(\mathrm{bs}^0(f) = O(1)\)
-
\(\mathrm{Q}_{\mathrm{E}}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}(f) = \Omega(n^{1/3})\) against \(\mathrm{sdeg}(f) = O(1)\)
-
\(\mathrm{Q}_{0}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^1(f_n) = O(1)\)from \(\mathrm{Q}_{0}(f) = \Omega(n^{1/3})\) against \(\mathrm{bs}^1(f) = O(1)\)
-
\(\mathrm{Q}^{\mathrm{rob}}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{Q}^{\mathrm{rob}}(f) = \Omega(n^{1/3})\) against \(\mathrm{PostQ}_{\varepsilon}(f) = O(1)\)
-
\(\mathrm{Adv}^{\pm}(f_n) \to \infty \ \text{ while } \ \widetilde{\deg}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{Adv}^{\pm}(f) = \Omega(n^{1/3})\) against \(\widetilde{\deg}_{\varepsilon}(f) = O(1)\)
-
\(\gamma_2^{\alpha}(f_n) \to \infty \ \text{ while } \ \widetilde{\deg}_{+}(f_n) = O(1)\)from \(\gamma_2^{\alpha}(f) = \Omega(n^{1/3})\) against \(\widetilde{\deg}_{+}(f) = O(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Omega(n^{2/3})\) against \(\mathrm{s}^0(f) = O(1)\)
… and 123 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
For every $q \ge n^{12}$ there is a partial $f : D \to \{0,1\}$ with $D \subseteq [q]^{3n}$, exact polynomial degree at most $9$, and $\mathrm{Q}(f) = \Omega(n^{1/3})$ -- constant degree against polynomial quantum query complexity. Binary-encoding the alphabet ($q$ the least power of two above $n^{12}$) gives a partial Boolean function on $N$ bits with $\deg = O(\log N)$ and $\mathrm{Q} = \widetilde\Omega(N^{1/3})$, i.e. $\mathrm{Q} = 2^{\Omega(\deg)}$.
-
The same construction, since $\widetilde{\deg} \le \deg \le 9$: exponential in the Boolean encoding, constant-vs-polynomial over an unbounded alphabet. A second proof, via a total search problem, is given by [BenDavidKundu24search].
-
The positive adversary is $O(\deg^2) = O(1)$ here, against $\mathrm{Q} = \Omega(n^{1/3})$; the lower bound genuinely needs negative weights.
Notes
The alphabet is what carries the separation: over $[q]$ with $q \ge n^{12}$ the exact degree is an absolute constant. Binary encoding costs a factor $\log q = \Theta(\log n)$ in the degree and only polylogarithmic factors in the input length, which is how the constant-vs-polynomial statement becomes an exponential one for Boolean functions.