Q The Query Complexity Zoo
\(\mathrm{forr}\)

FORRELATION

One quantum query vs $\widetilde\Theta(\sqrt n)$ randomized queries -- the maximal possible gap at $\mathrm{Q}=1$.

partial quantum arity: $2n$ bits (two strings $x,y \in \{\pm1\}^n$)— also: Fourier correlation, 2-forrelation

Description

Decide whether $y$ is highly correlated with the Fourier transform of $x$.

Formal definition

For $x, y \in \{-1,1\}^n$ with $n=2^m$, let $$\Phi(x,y) \;=\; \frac{1}{n^{3/2}}\sum_{i,j\in\{0,1\}^m} x_i\,(-1)^{i\cdot j}\,y_j \;=\; \frac{1}{\sqrt n}\,\langle \hat x, y\rangle .$$ $\mathrm{forr}(x,y) = 1$ if $\Phi(x,y) \ge 3/5$, $= 0$ if $|\Phi(x,y)| \le 1/100$, and undefined otherwise.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(1\) Prepare uniform superposition, query $x$, Hadamard, query $y$, Hadamard, measure. AaronsonAmbainis18
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(O(1)\) $\widetilde{\deg}\le 2\mathrm{Q} = 2$.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\widetilde\Theta(\sqrt n)\) Lower bound $\Omega(\sqrt n/\log n)$ [AaronsonAmbainis18], improved to $\widetilde\Omega(\sqrt n)$ via Fourier growth of decision trees [Tal20]. Matching $O(\sqrt n)$ upper bound. AaronsonAmbainis18 Tal20
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(n)\)
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(0\) putative The support of a product distribution is a combinatorial rectangle $\prod_i S_i$, and no rectangle inside the promise can meet both sides. Flipping one bit of $x$ or $y$ moves $\Phi$ by at most $2/\sqrt n$, since $|\partial\Phi/\partial x_i| = n^{-3/2}\big|\sum_j (-1)^{i\cdot j}y_j\big| \le n^{-1/2}$. So if the rectangle held a $1$-input ($\Phi \ge 3/5$) and a $0$-input ($|\Phi| \le 1/100$) one could walk between them inside the rectangle one bit at a time, and for $n \ge 16$ some intermediate point -- also in the rectangle -- would have $\Phi$ in the forbidden band $(1/100, 3/5)$, off the promise. Hence every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \widetilde\Theta(\sqrt n)$. This collapse is generic for promise problems, not special to forrelation: it recurs at \(\mathrm{SIMON}_n\), \(\mathrm{BV}_n\), \(\mathrm{COL}_n\), \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{ApproxIndex}_k\), and it is why $\mathrm{RS}(g) = \widetilde\Omega(\mathrm{D}^{\mathrm{prod}}(g))$ is stated only for total $g$.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(1)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = 1$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\mathrm{Adv}^{\pm}(f) = \Theta(1)$ and $\mathrm{Q}_{\varepsilon}(f) = 1$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\widetilde\Theta(\sqrt n)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon}(f) = \widetilde\Theta(\sqrt n)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(1)\) A lower bound on $\mathrm{Q} = 1$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\widetilde\Theta(\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \widetilde\Theta(\sqrt n)$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\Theta(n)\) Between $\mathrm{D} = \Theta(n)$ and the trivial $2n$.
\(\mathrm{s}(f)\) Sensitivity \(0\) putative The promise gap is wider than one flip. Flipping a single $x_i$ changes $\Phi$ by $\tfrac{2}{n^{3/2}}\big|\sum_j (-1)^{i\cdot j} y_j\big| \le 2/\sqrt n$, and the same bound holds for a $y_j$; the two promise regions are separated by $3/5 - 1/100$. So for $n \ge 12$ no single flip stays inside the promise with a different value, and $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = \Theta(n)$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) putative See $\mathrm{s}$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) putative See $\mathrm{s}$.
\(\lambda(f)\) Spectral sensitivity \(0\) putative The sensitivity graph on the promise has no edges (see $\mathrm{s} = 0$), so the adjacency matrix is zero. Spectral sensitivity lower-bounds $\mathrm{Q}$ for total functions and says nothing at all here.
\(\mathrm{bs}(f)\) Block sensitivity \(O(1)\) Two arguments, the second much sharper. Counting: flipping $m$ coordinates moves $\Phi$ by at most $2m/\sqrt n$, so every sensitive block has $\Omega(\sqrt n)$ coordinates and at most $O(\sqrt n)$ of them are disjoint. Adversary: $\mathrm{bs}(f) \le \mathrm{Adv}(f)^2$ holds for partial $f$ as well (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\) -- disjointness of the blocks is all the proof uses), and $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$ here. So block sensitivity is constant against $\mathrm{D} = \Theta(n)$, and it does not even see the $\widetilde\Theta(\sqrt n)$ scale of $\mathrm{R}$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(O(1)\) See $\mathrm{bs}$: $\mathrm{bs}^0 \le \mathrm{bs} = O(1)$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(O(1)\) See $\mathrm{bs}$: $\mathrm{bs}^1 \le \mathrm{bs} = O(1)$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(O(1)\) The fractional relaxation is constant too, by the quantum certificate route rather than by counting: $\mathrm{fbs}(f) = \Theta(\mathrm{RC}(f)) = \Theta(\mathrm{QC}(f)^2)$ for partial $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{QC} \le \mathrm{Q} = 1$ since an algorithm computing $f$ also verifies its input. The load count of the $\mathrm{bs}$ entry only gives $O(\sqrt n)$; this is the right answer.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(O(1)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(O(1)\) $\mathrm{RC} = \Theta(\mathrm{fbs}) = O(1)$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(1)\) An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$; and $\mathrm{QC} \ge 1$ for a non-constant $f$. This is what forces $\mathrm{fbs} = O(1)$ above, via $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$.
\(\mathrm{sdeg}(f)\) Sign degree \(\Theta(1)\) Sandwiched: $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(1)$, and at least $1$. Every degree measure below $\widetilde{\deg}$ is constant here while $\mathrm{R} = \widetilde\Theta(\sqrt n)$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(1)\) Sandwiched between $\mathrm{sdeg} = \Theta(1)$ and $\widetilde{\deg} = O(1)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\Theta(1)\) A polynomial is a rational function with denominator $1$, so $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg} = O(1)$; and at least $1$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$. Post-selection is of no use on a problem already solved by one query.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\widetilde O(\sqrt n)\) Sandwiched: $\widetilde{\deg} \le \mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon$, i.e. between $O(1)$ and $\widetilde\Theta(\sqrt n)$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\widetilde O(\sqrt n)\) The classical adversary lower-bounds $\mathrm{R} = \widetilde\Theta(\sqrt n)$ (via $\mathrm{CA} \le \mathrm{prt}_\varepsilon + \log(1/\varepsilon) \le 2\mathrm{R}_\varepsilon + O(1)$). It is at least $\Omega(\mathrm{fbs})$, which is only $\Omega(1)$ here, so nothing pins it further.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\widetilde O(\sqrt n)\) The public-coin, entangled and non-signaling certificate games all collapse to $\Theta(\mathrm{CA})$ (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)). CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\widetilde O(\sqrt n)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants; see \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\). CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\widetilde O(\sqrt n)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants; see \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\). CGLMSG23
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\widetilde\Omega(\sqrt n)\) Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\widetilde\Omega(\sqrt n)$ here.
\(\mathrm{RS}(f)\) Sabotage complexity \(\widetilde O(\sqrt n)\) From the partial-function chain $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$. Nothing pins it from below: $\mathrm{CA} \le \mathrm{RS}$ is the only lower bound available and $\mathrm{CA}$ itself is unpinned here.
\(\chi(f)\) Conflict complexity \(\widetilde O(\sqrt n)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$ for partial $g$. The familiar lower bound $\chi = \Omega(\mathrm{bs})$ is a total-function statement [Li18] and gives only $\Omega(1)$ here in any case, since $\mathrm{bs} = O(1)$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\widetilde O(\sqrt n)\) $\mathrm{R}^{*} \le \mathrm{R}$ for partial $f$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \widetilde\Omega(n^{1/4})$ and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(1)$, so the composition-friendly version of $\mathrm{R}$ is still polynomially far above the single quantum query.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\widetilde O(\sqrt n)\) At most $\mathrm{R}$. The reverse direction is only $\mathrm{R} = 2^{\Omega(\mathrm{noisyR})}$, which permits $\mathrm{noisyR}$ to be as small as $\Omega(\log n)$; cf. \(\mathrm{ApproxIndex}_k\), where that exponential gap is realised.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(1)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$, and $\mathrm{Q} = 1$. So even an oracle whose every answer is only a bounded-error bit is beaten by $O(1)$ quantum queries, against $\mathrm{R} = \widetilde\Theta(\sqrt n)$ and $\mathrm{N}_p = \widetilde\Theta(\sqrt n)$ classically.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\widetilde\Omega(n^{1/4})\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$, and $\mathrm{R} = \widetilde\Theta(\sqrt n)$; the upper end is $\mathrm{LR} \le \mathrm{R}$. Even the linearised measure, which charges $1/\gamma$ instead of $1/\gamma^2$ for bias $\gamma$, stays polynomially above $\mathrm{Q} = 1$.
\(\bar{\chi}(f)\) Max-conflict complexity \(\widetilde\Omega(n^{1/4})\) $\mathrm{R} = O(\bar\chi^2)$ for partial $g$, so $\bar\chi = \Omega(\sqrt{\mathrm{R}}) = \widetilde\Omega(n^{1/4})$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\widetilde\Theta(\sqrt n)\)· putative The $O(\sqrt n)$ algorithm samples coordinates of $x$ and $y$ from its coins and forms an estimator of $\langle\hat x, y\rangle$, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \widetilde\Theta(\sqrt n)$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\widetilde\Omega(\sqrt n)\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, i.e. between $\widetilde\Theta(\sqrt n)$ and $\Theta(n)$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\widetilde\Theta(\sqrt n)\) At least $\mathrm{R}$, and at most $O(\mathrm{R})$ by reading each sampled coordinate $O(1)$ times and majority-voting.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\widetilde O(\sqrt n)\) From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\widetilde O(\sqrt n)\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\widetilde\Theta(\sqrt n)\) Degenerate on a partial Boolean function: there is only one correct answer, so the canonical solution function is forced to be $f$ itself and reproducibility is free. Hence $\mathrm{psD} = \Theta(\mathrm{R}) = \widetilde\Theta(\sqrt n)$ -- see the \(\mathrm{psD}(S)\) entry.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(O(1)\) Degenerate on a Boolean function: every input is critical and the solution function is forced, so $\mathrm{cbs} = \mathrm{bs} = O(1)$. GoosPitassi14
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n)\) putative Upper: $\mathrm{C} \le 2n$. Lower, from one explicit $1$-input. Take $n = 2^m$ with $m$ even and let $x$ be a bent function on $m$ bits, so $\hat x_j = \pm n^{-1/2}$ for every $j$; put $y_j = \sqrt n\,\hat x_j \in \{\pm1\}$. Then $\Phi = \tfrac{1}{\sqrt n}\sum_j \hat x_j y_j = 1$, a $1$-input. Dually $\hat y_i = x_i/\sqrt n$, so $\Phi = \tfrac{1}{\sqrt n}\sum_i x_i \hat y_i$ and flipping any single $x_i$ lowers $\Phi$ by exactly $2/n$; flipping $t$ of them gives $\Phi = 1 - 2t/n$ exactly. Choosing $t$ near $n/2$ lands in $|\Phi| \le 1/100$, a $0$-input. So a certificate at this input must fix all but at most $0.51n$ of the $n$ coordinates of $x$, i.e. $\mathrm{C}^1 \ge 0.49n$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(n)\) putative The lower bound recorded under \(\mathrm{C}(f)\) is witnessed at a $1$-input, so $\mathrm{C}^1 = \Theta(n)$ as well.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(n)\) putative Take the same bent $x$ and $y = \chi_{j_0}$, i.e. $y_j = (-1)^{j\cdot j_0}$. Then $\sum_j \hat x_j y_j = x_{j_0} = \pm1$, so $|\Phi| = 1/\sqrt n \le 1/100$ and this is a $0$-input. Since $\sum_j |\hat x_j| = \sqrt n$ and $\sum_j \hat x_j y_j = \pm 1$, the number of $j$ with $y_j \ne \mathrm{sign}(\hat x_j)$ is $n/2 \pm \sqrt n/2$, and flipping any one of them raises $\Phi$ by exactly $2/n$. Flipping $0.31n$ of them reaches $\Phi \ge 3/5$, so a certificate must fix at least $n/2 - \sqrt n - 0.31n \ge 0.18n$ of the $y$-coordinates. With $\mathrm{C}^0 \le 2n$ this gives $\Theta(n)$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(n)\)· putative Every certificate, at every promise input, fixes $\Omega(n)$ coordinates. Suppose one fixes fewer than $10^{-3}n$; then at least $0.999n$ coordinates of $x$ and $0.999n$ of $y$ are free, and by Cauchy--Schwarz the fixed $y$-positions carry $\sum_{\text{fixed } j}|\hat x_j| \le \sqrt{10^{-3}n} \le 0.032\sqrt n$. At a $1$-input, $\Phi \ge 3/5$ forces $\sum_j |\hat x_j| \ge 0.6\sqrt n$; setting every free $y_j$ to $-\mathrm{sign}(\hat x_j)$ drives $\Phi$ below $-0.5$, and reverting those bits one at a time back to their original values moves $\Phi$ in steps of $2|\hat x_j|/\sqrt n \le 2/\sqrt n < 1/50$ up to $\Phi \ge 3/5$, so some intermediate assignment has $|\Phi| \le 1/100$ -- a $0$-input consistent with the certificate. At a $0$-input, set the free $x$-coordinates uniformly at random: then $\sum_j |\hat x_j| \ge 0.7\sqrt n$ with high probability, and setting every free $y_j$ to $\mathrm{sign}(\hat x_j)$ gives $\Phi \ge 0.7 - 2(0.032) > 3/5$, a $1$-input consistent with the certificate. Either way the set was not a certificate. With $\mathrm{C}_{\min} \le \mathrm{C} \le 2n$ this pins $\Theta(n)$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) Squeezed: $\mathrm{C} \le \mathrm{SP} = \mathrm{UC} \le \mathrm{D}$, and both ends are $\Theta(n)$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) Equal to $\mathrm{UC}$ exactly, and squeezed between $\mathrm{C} = \Theta(n)$ and $\mathrm{D} = \Theta(n)$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) Squeezed between $\mathrm{C}_{\min} = \Theta(n)$ and $\mathrm{UC} = \Theta(n)$. Note this is the one-sided minimum $\min\{\mathrm{UC}^0,\mathrm{UC}^1\}$, and both sides are already $\Theta(n)$ here.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(n)\) A tree of rank $r$ has a leaf at depth $\le r$, so $\mathrm{C}_{\min} \le \mathrm{rank} \le \mathrm{D}$; both ends are $\Theta(n)$.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n)}\) At least $2^{\mathrm{C}_{\min}}$ and at most $2^{\mathrm{D}+1}$, and $\mathrm{C}_{\min} = \Theta(\mathrm{D}) = \Theta(n)$. Unlike \(\mathrm{DJ}_n\), no small tree exists: the promise here has no cheap side.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(O(n^{3/4})\) putative Exhibiting a weighting directly, as one must off the promise ($\mathrm{EC} \le \mathrm{C}$ needs totality). Flipping one bit of $x$ or $y$ moves $\Phi$ by at most $2/\sqrt n$, so two promise inputs of opposite value differ in at least $(3/5-1/100)\sqrt n/2 \ge 0.29\sqrt n$ coordinates. Put $w^x_i = (0.29\sqrt n)^{-1/2}$ at every input and every coordinate: then $\sum_{i: x_i \ne y_i} w^x_i w^y_i \ge 1$, and the cost is $2n \cdot \Theta(n^{-1/4}) = \Theta(n^{3/4})$. This beats the trivial $\mathrm{EC} \le \mathrm{C} = \Theta(n)$; from below only $\mathrm{EC} \ge \mathrm{FC} = O(1)$ is available.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(O(n^{3/2})\) putative Private coins, so no shared index is available and the total-function ceiling $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not licensed here. Both players output a uniformly random one of the $2n$ positions; since opposite-valued promise inputs differ in $\ge 0.29\sqrt n$ positions the win probability is $\ge 0.29\sqrt n/(2n)^2$, so $\mathrm{CG} = O(n^{3/2})$. From below $\mathrm{CG} \ge \mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA})$, which is only $\Omega(1)$ here.
\(\deg(f)\) Exact degree \(O(n)\) At most $\mathrm{D} = \Theta(n)$. Nothing smaller is known: unlike $\widetilde{\deg} = O(1)$, exact representation cannot exploit the gap between the two promise bands.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(O(n)\) At most $\mathrm{C}^1 = \Theta(n)$: the sum over $1$-certificates of their indicator polynomials is a nondeterministic polynomial.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(O(n)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg} = O(n)$. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(O(n)\) At most $\mathrm{C} = \Theta(n)$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(O(n)\) At most $\mathrm{D} = \Theta(n)$, at least $\mathrm{Q} = 1$. The $\mathrm{Q}_E \ge \deg/2$ bound gives nothing, since $\deg$ itself is only known to be $O(n)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(O(n)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(n)$.

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. 379 in total, strongest first.

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

Separations it witnesses

Cited as a witness by

Notes

Aaronson-Ambainis also proved the matching upper bound: any partial $f$ with $\mathrm{Q}(f)=k$ has $\mathrm{R}(f) = O(n^{1-1/(2k)})$. So Forrelation is optimal, and $k$-Forrelation extends this to every $k$.