Q The Query Complexity Zoo
\(\mathrm{TSAT}_n\)

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

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

… and 123 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

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.