Q The Query Complexity Zoo
\(\mathrm{SURJ}_{N,R}\)

Surjectivity

The only known natural function separating $\mathrm{Q}$ from $\widetilde{\deg}$: $\widetilde{\deg} = \tilde\Theta(n^{3/4})$ while $\mathrm{Q} = \tilde\Theta(n)$.

total quantum arity: a list of $N$ elements of $[R]$ in binary, so $n = N\log_2 R$ bits; canonically $R = N/2$

Description

Read the input as a list $x_1,\dots,x_N \in [R]$ and accept iff every value in the range is hit, $\{x_1,\dots,x_N\} = [R]$. With $R$ a power of two and each $x_i$ written in binary this is a total Boolean function on $n = N\log_2 R$ bits, computed by a depth-3 $\mathrm{AC}^0$ circuit with logarithmic bottom fan-in. The problem is trivial for $R > N$; the interesting regime is $R = N/2$.

Two encodings appear in the literature and they differ by a $\log R$ factor. [Sherstov21] works over the one-hot domain, where $\mathrm{SURJ}_{n,r} = \mathrm{AND}_r \circ \mathrm{OR}_n$ restricted to Hamming weight $\le n$; [BKT18] and [BT22] use the binary encoding above. [BT22, Obs. 52 and Lem. 54] relate the two -- which is where the tildes below come from.

Formal definition

$$\mathrm{SURJ}_{N,R}(x) \;=\; \bigwedge_{j\in[R]}\ \bigvee_{i\in[N]}\ [\,x_i = j\,].$$

Measure values

MeasureValueNotes
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\tilde\Theta(n^{3/4})\) At $R = N/2$. Upper: [Sherstov21, Thm. 1.3] constructs a polynomial of degree $O(\sqrt n\,r^{1/4})$ for $r \le n$; [BKT18, Thm. 3.1] restates it as $\tilde O(N^{3/4})$ for every $R$. Lower: [BKT18, Thm. 4.1], $\tilde\Omega(R^{3/4})$ for some $N = O(R)$. In general $\widetilde{\deg}(\mathrm{SURJ}_{N,R}) = \tilde\Theta(R^{1/4}N^{1/2})$. The $\varepsilon$-dependence is $\tilde\Theta(n^{3/4}\log^{1/4}(1/\varepsilon))$ for $3^{-n} \le \varepsilon \le 1/3$ [SherstovThaler23]. Sherstov21 BKT18 BT22
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\tilde\Theta(n)\) Lower: [BeameMachmouchi12, Cor. 3] gives $\Omega(n/\log n)$ -- their Cor. 2 shows $\Omega(N)$ element queries for $\mathrm{ONTO}$ with $[2N-2]\to[N]$, and the binary encoding costs the log. Upper: $n$, trivially. A clean $\Omega(n)$ is widely attributed to [Sherstov18asymmetry], but that paper states it only as a confidence in Remark 3.4 ("we are confident that ... one can eliminate the logarithmic factors"), not as a theorem, and about some $\mathrm{AC}^0$ function rather than $\mathrm{SURJ}$ in the binary encoding; hence the tilde. BeameMachmouchi12
\(\mathrm{sdeg}(f)\) Sign degree \(\tilde\Theta(\sqrt n)\) [BunThaler21largeerror, Thm. 1.1]: $\deg_{\pm}(\mathrm{SURJ}_{N,R}) = \tilde\Theta(\min\{R,\sqrt N\})$ for $R < N/2$, which at the canonical $R$ is $\tilde\Theta(\sqrt n)$; also [BT22, Thm. 57]. Their Cor. 1.2 turns this into an $\mathrm{AC}^0$ function with unbounded-error communication complexity $\tilde\Omega(\sqrt n)$. BunThaler21largeerror BT22
\(\mathrm{s}(f)\) Sensitivity \(\Theta(n)\) putative At $R = N/2$ take the list in which each of $1,\dots,R-1$ occurs exactly once and $R$ fills the remaining $R+1$ slots: a $1$-input on which flipping any bit of any uniquely-occurring element deletes that value from the range, so $\mathrm{s} \ge (R-1)\log_2 R = n/2 - O(\log n)$. And $\mathrm{s}\le n$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(n/\log n)\) putative Exactly $N$, the number of slots, which at $R = N/2$ is $n/\log_2 R = \Theta(n/\log n)$. Upper: a $0$-input misses some value $u$, and forcing $x_i \ne u$ costs a single bit per slot -- fix one position where $x_i$ and $u$ disagree. Lower: take the $0$-input in which every value except $u$ occurs at least twice; then for each slot $i$ the input obtained by rewriting $x_i$ to $u$ is surjective, so the certificate must fix a bit in every slot. Verified by exhaustive search at $R = 4$, $N = 8$, where $\max_x \mathrm{C}_x = 8 = N$ over all $0$-inputs. (An earlier version of this entry said $n$; that over-counts by a factor $\log R$ -- one does not have to pin down each $x_i$, only to keep it away from $u$.)
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(n)\) putative A $1$-certificate names one preimage for each of the $R$ range values, which is $R\log_2 R = n/2$ bits at $R = N/2$, and that suffices.
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{bs}(f) \le n$, with $\mathrm{s} = \Theta(n)$ here.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le 3\,\mathrm{R}(f) \le 3n$, and $\mathrm{bs} = \Theta(n)$ here. (The $\mathrm{Q} \le \mathrm{R}$ route would only give $\tilde\Theta(n)$; block sensitivity removes the log.)
\(\deg(f)\) Exact degree \(n\) putative Full degree, for every power of two $R \ge 2$ and every even $N \ge R$ -- in particular at $R = N/2$. The coefficient of the top monomial $\prod_i x_i$ is $\pm\sum_x(-1)^{|x|}\mathrm{SURJ}(x)$. Inclusion-exclusion over the missed set gives $\sum_x(-1)^{|x|}\mathrm{SURJ}(x) = (-1)^N\sum_{S\subseteq[R]}(-1)^{|S|}\sigma(S)^N$ with $\sigma(S) = \sum_{v\in S}(-1)^{|v|}$, because $\sum_{v\in[R]}(-1)^{|v|} = 0$. Splitting $S$ by the parity of its elements and passing to exponential generating functions turns this into $N!\,[z^N]\big((1-e^z)(1-e^{-z})\big)^{R/2} = N!\,[z^N]\big(-4\sinh^2(z/2)\big)^{R/2}$, and expanding $\sinh$ leaves $\pm R!\,T(N,R)$, where $T$ is the central factorial number of the second kind. $T(N,R) > 0$ whenever $N \equiv R \bmod 2$ and $N \ge R$, which holds here since $R$ is even. Checked numerically at $R=2,N=4$ (coefficient $-2$) and $R=4,N=8$ (coefficient $504 = 4!\cdot T(8,4)$).
\(\mathrm{D}(f)\) Deterministic query complexity \(n\) Evasive: $\deg(f) \le \mathrm{D}(f) \le n$ and $\deg = n$ here, so every deterministic tree must read all $n$ bits on some input. This settles the question the previous version of this entry left open, but only as strongly as the $\deg$ computation above.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The $\mathrm{s}$ end is itself an unpublished argument (see above), so this is only as good as that.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The $\mathrm{s}$ end is itself an unpublished argument (see above), so this is only as good as that.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The $\mathrm{s}$ end is itself an unpublished argument (see above), so this is only as good as that.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The $\mathrm{s}$ end is itself an unpublished argument (see above), so this is only as good as that.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CA}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Omega(n),\ O(n^2/\log n)\) The old reading $\mathrm{bs} \le \mathrm{CG} \le \mathrm{D}$ was wrong on the right: $\mathrm{CG}$ is not capped by the arity. The correct sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0, \mathrm{CA}\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]. Here $\mathrm{R}_0 = \Theta(n)$ from below, and $\mathrm{C}^0\mathrm{C}^1 = \Theta(n/\log n)\cdot\Theta(n)$ from above. The $\mathrm{Adv}$ route gives nothing extra, since only $\mathrm{Adv} = O(n/\sqrt{\log n})$ is recorded. The gap is genuine and left open. CGLMSG23
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional. The lower end also inherits the provenance of $\mathrm{s}$ on this page.
\(\mathrm{s}^1(f)\) 1-sensitivity \(\Theta(n)\) putative The $\mathrm{s} = \Theta(n)$ witness on this page is a $1$-input, so the maximum is carried by the $1$-side: $\mathrm{s}^1 \ge (R-1)\log_2 R = n/2 - O(\log n)$. Exhaustive check at $R=4$, $N=8$: $\mathrm{s}^1 = 6 = (R-1)\log_2 R$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\Theta(n/\log n)\) putative A factor $\log n$ below $\mathrm{s}^1$. Upper: at a $0$-input, a single flip can only change one slot, so it can only add one value to the range; hence exactly one value $u$ may be missing and each slot has at most one sensitive bit, giving $\mathrm{s}^0 \le N = \Theta(n/\log n)$. Lower: take $u = 0^r$, cover the $R-1-r$ values of Hamming weight $\ge 2$ with one slot each and fill the remaining $N-R+1+r$ slots with duplicated weight-one values; flipping the single $1$ of any of those slots produces $u$ and loses nothing. Exhaustive check at $R=4$, $N=8$: $\mathrm{s}^0 = 7 = N-R+1+r$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\Theta(n)\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{bs}^1(f) \le n$, with $\mathrm{s}^1 = \Theta(n)$ here. (At $R=4$, $N=8$ the exhaustive value is $\mathrm{bs}^1 = 8 = n/2 = \mathrm{C}^1$.)
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(n/\log n)\) putative Upper: a sensitive block $B$ at a $0$-input must create every missing value, so fix one missing $u$ and map $B$ to the least slot $i$ with $(x\oplus B)_i = u$; two disjoint blocks cannot share that slot, since both would have to restrict to the same nonzero pattern $x_i \oplus u$ there. Hence $\mathrm{bs}^0 \le N$. Lower: $\mathrm{s}^0 = \Theta(N)$. So $\mathrm{bs}^0 = \Theta(N) = \Theta(n/\log n)$, and the block-sensitivity asymmetry matches the certificate asymmetry $\mathrm{C}^0 = N$ against $\mathrm{C}^1 = n/2$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(n/\log n)\) putative Upper: $\mathrm{C}_{\min} \le \mathrm{C}^0 = N$. Lower: in any certificate at most $R-1$ slots can be left entirely unfixed -- $R$ free slots could be set to $1,\dots,R$ and make the input surjective -- so every certificate touches at least $N-R+1 = R+1$ slots, and $\mathrm{C}_{\min} \ge R+1 = \Theta(N)$. The $1$-side is more expensive ($\mathrm{C}^1 = n/2$), so the minimum is attained on $0$-inputs.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(n)\) Squeezed between $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, both $\Theta(n)$ here.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) Squeezed between $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with $\mathrm{C} = \Theta(n)$ and $\mathrm{D} = n$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) Squeezed between $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C} = \Theta(n)$ and $\mathrm{D} = n$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Every bit is relevant -- permute the list so that the slot in question holds a uniquely-occurring value, and flipping any of its bits changes the answer -- so for a total function the non-adaptive cost is the full $n$. Consistent with $\mathrm{D} = \mathrm{D}^{\mathrm{na}} = n$: adaptivity buys nothing here.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$ here.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(n)$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\tilde\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon} = \tilde\Theta(n)$ and $\mathrm{D} = n$ here.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\tilde\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{Q}_{\mathrm{E}}(f)$, both $\tilde\Theta(n)$ here.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\tilde\Theta(n)\) $\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) = \tilde\Theta(n)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\tilde\Theta(n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \tilde\Theta(n)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\tilde\Theta(n)\) Same sandwich as \(\mathrm{Adv}^{\pm}(f)\): the multiplicative adversary is also a tight characterisation of $\mathrm{Q}$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$ (\(\mathrm{QC}(f)\) vs \(\mathrm{FC}(f)\)), and $\mathrm{FC} = \Theta(n)$ here.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(n/\sqrt{\log n})\) putative The certificate-complexity barrier: $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0(f)\,\mathrm{C}^1(f)}$ for total $f$, and here that is $\sqrt{N \cdot n/2} = \Theta(n/\sqrt{\log n})$. Only a $\sqrt{\log n}$ factor short of $\mathrm{Q}$, so unlike \(\mathrm{ED}_n\) and \(\mathrm{COL}_n\) the positive-weights adversary is not badly broken on surjectivity -- but it cannot reach $\mathrm{Q} = \tilde\Theta(n)$ either. A floor: $\mathrm{Adv} \ge \lambda \ge \sqrt{\mathrm{s}} = \Omega(\sqrt n)$.
\(\lambda(f)\) Spectral sensitivity \(\Omega(\sqrt n),\ O(n/\sqrt{\log n})\) putative Lower: $\lambda \ge \sqrt{\mathrm{s}} = \Omega(\sqrt n)$ -- a star of degree $\mathrm{s}$ sits inside the sensitivity graph -- which here is the same bound Huang's $\lambda \ge \sqrt{\deg}$ gives, since $\deg = n$. Upper: the sensitivity graph is bipartite between $0$- and $1$-inputs with side degrees $\mathrm{s}^0$ and $\mathrm{s}^1$, so $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{\Theta(n/\log n)\cdot\Theta(n)} = O(n/\sqrt{\log n})$ -- the same ceiling the certificate barrier puts on $\mathrm{Adv}$, and for the same asymmetry reason. Which end is the truth is open.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(n\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\tilde\Theta(n)\) Between $\mathrm{Q} = \tilde\Theta(n)$ and the universal ceiling $\mathrm{Q}^{\mathrm{rob}} \le O(n)$ of Buhrman-Newman-Röhrig-de Wolf, who recover all $n$ bits from $O(n)$ noisy queries. Noise is free here because the problem is already maximally hard.
\(\mathrm{DTsize}(f)\) Decision tree size \(\Omega(2^{n/\log n}),\ O(2^n)\) putative Lower: a tree with $L$ leaves has one at depth $\le \log_2 L$ (Kraft), and a leaf at depth $t$ is a certificate of size $t$, so $\log_2 L \ge \mathrm{C}_{\min} = \Theta(n/\log n)$. Upper: the complete tree. The $\log n$ in the exponent is exactly the gap between $\mathrm{C}_{\min} = \Theta(N)$ and $\mathrm{D} = n = N\log_2 R$, i.e. the fact that a $0$-certificate spends one bit per slot rather than $\log R$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(2^{-\Theta(n/\log n)}\) putative Exponentially small, because surjectivity is exponentially rare: $N = 2R$ uniform draws into $R$ bins cover them all with probability $p = e^{-\Theta(R)} = 2^{-\Theta(n/\log n)}$, and the uniform measure on $\{0,1\}^n$ is the uniform measure on lists since $R$ is a power of two. Upper: $\mathrm{Inf}_i \le \Pr[f(x)=1]+\Pr[f(x^{\oplus i})=1] = 2p$, so $\mathrm{I}(f) \le 2np = 2^{-\Theta(n/\log n)}$. Lower: Poincare, $\mathrm{I}(f) \ge \mathrm{Var}(f) = 4p(1-p) = \Theta(p)$. So $\mathrm{I} = \Theta(1)$ fails badly while $\mathrm{D} = n$: total influence says nothing about query complexity for biased functions.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(2^{-\Theta(n/\log n)}\) For Boolean-valued $f$ the $L_1$ and $L_2$ influences coincide (\(\mathrm{I}^{1}(f)\)), so this is the $\mathrm{I}(f)$ row verbatim.
\(\mathrm{MaxInf}(f)\) Maximum influence \(2^{-\Theta(n/\log n)}\) Between $\mathrm{I}(f)/n$ and $\mathrm{I}(f)$, both $2^{-\Theta(n/\log n)}$ since the factor $n$ is swallowed by the exponent.
\(\mathrm{Var}(f)\) Variance \(2^{-\Theta(n/\log n)}\) From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. A uniform input is surjective with doubly negligible probability, so the whole Fourier picture is about the bias; the ratio to $\mathrm{MaxInf}$ is not pinned, so \(\mathrm{osss}(f)\) is not recorded.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) putative Upper: $\mathrm{RS}(f)\le\mathrm{R}(f)=\Theta(n)$ for total $f$ [BenDavidKothari18]. Lower: take the surjective input that puts value $v$ in slot $v$ for $v\le R$ and value $1$ in the other $R$ slots. Starring any one bit of any of the first $R$ slots sabotages it: flipping that bit turns slot $v$ into a slot holding some other value $w\ne v$, which is still covered elsewhere, so the value $v$ goes missing and surjectivity flips. Those $R\log_2 R=\Theta(n)$ sabotaged inputs share one base assignment and each has a unique star, so finding a star is finding a marked coordinate among $\Theta(n)$. BenDavidKothari18
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) $\mathrm{noisyR}\le\mathrm{R}=\Theta(n)$ [BenDavidBlais20composition], and here $\mathrm{R}=\Theta(n)$ is $\Theta(\text{arity})$, which forces $\mathrm{noisyR}=\Theta(\mathrm{R})$ [CKMPSS23]. Cheap biased queries do not help: the hard part is coverage, not accuracy. CKMPSS23 BenDavidBlais20composition
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\)· putative Upper: $\mathrm{D}^{\mathrm{prod}}\le\mathrm{R}=\Theta(n)$ (also $\widetilde O(\mathrm{RS})$ [Sanyal24]). Lower: point masses are product measures, so fix slots $1,\dots,R-1$ to the values $1,\dots,R-1$ and give each of the remaining $R+1$ slots independent bits, each $1$ with probability $1-1/\log_2 R$ except the last, which is $1$ with probability $e/(R+1)$. Then a free slot equals the one uncovered value (the all-ones codeword) with probability $1/(R+1)$, so the answer is balanced, and resolving one free slot costs $\Theta(\log R)$ bits in expectation because a $0$ is rare. Any tree must resolve a constant fraction of the $R+1$ slots, giving $\Omega(R\log R)=\Omega(n)$. Sanyal24
\(\deg_2(f)\) Mod-2 degree \(\Theta(n)\) putative Restrict: fix slots $1,\dots,R-1$ to the values $1,\dots,R-1$, encode the remaining value $R$ by the all-ones codeword, and leave the other $R+1$ slots free. Any non-all-ones codeword names an already covered value, so the restriction is exactly $\mathrm{OR}_{R+1}\circ\mathrm{AND}_{\log_2 R}$ on $(R+1)\log_2 R=\Theta(n)$ free bits. Over $\mathbb{F}_2$ that is $1+\prod_i(1+\prod_j x_{ij})$, whose top monomial is the product of every free bit, so $\deg_2\ge(R+1)\log_2 R$. Mod-$2$ degree never increases under restriction, and $\deg_2\le n$.
\(\deg_p(f)\) Mod-p degree \(\Theta(n)\) putative Same restriction as \(\deg_2(f)\): over $\mathbb{F}_p$ the restriction $\mathrm{OR}_{R+1}\circ\mathrm{AND}_{\log_2 R}$ is $1-\prod_i(1-\prod_j x_{ij})$, whose top monomial has coefficient $\pm1\ne0$, so $\deg_p\ge(R+1)\log_2 R=\Theta(n)$; and $\deg_p\le\deg=n$.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(n)\) A depth-$t$ parity tree writes $f$ over $\mathbb{F}_2$ as a sum of products of at most $t$ affine forms, so $\deg_2\le\mathrm{D}^{\oplus}$; with $\deg_2=\Theta(n)$ and $\mathrm{D}^{\oplus}\le\mathrm{D}=n$ there is no room. Parity queries buy nothing on surjectivity.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(\Theta(n)\) $\mathrm{D}^{\oplus}(f)\le\dim_{\mathbb{F}_2}(f)\le n$ (\(\dim_{\mathbb{F}_2}(f)\) vs \(\mathrm{D}^{\oplus}(f)\)), and $\mathrm{D}^{\oplus}=\Theta(n)$ here.
\(\mathrm{spar}(f)\) Fourier sparsity \(2^{\Theta(n)}\) putative Sparsity never increases under restriction, since the Fourier support of a restriction is a projection of the original support. On the restriction of the \(\deg_2(f)\) entry, $\pm1$-valued $f=1-2\prod_i(1-\mathrm{AND}_{\log_2 R})$: the blocks are disjoint, every one of the $2^{\log_2 R}$ coefficients of $1-\mathrm{AND}$ is nonzero, and coefficients multiply, so the product has $2^{(R+1)\log_2 R}=2^{\Theta(n)}$ nonzero coefficients. The ceiling is $2^n$.
\(\hat{L}_1(f)\) Spectral norm \(2^{\Omega(n/\log n)},\ O(2^n)\) On the restriction of the \(\deg_2(f)\) entry the spectral norm multiplies over the disjoint blocks: $\hat L_1(\prod_i(1-\mathrm{AND}_s))=(2-2^{1-s})^{R+1}$ with $s=\log_2 R$, and $\hat L_1(1-2P)\ge2\hat L_1(P)-1$, so $\hat L_1\ge2^{\Omega(R)}=2^{\Omega(n/\log n)}$. Restriction can only decrease $\hat L_1$. The ceiling is $\hat L_1\le2^{\mathrm{D}}=2^n$ (\(\hat{L}_1(f)\) vs \(\mathrm{D}(f)\)).
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(2^{-\Theta(n/\log n)}\) Sandwiched by the two recorded influence values: $\delta\,\mathrm{MaxInf}\le\mathrm{NS}_\delta\le\delta\,\mathrm{Inf}$, and both $\mathrm{Inf}$ and $\mathrm{MaxInf}$ are $2^{-\Theta(n/\log n)}$ here. A random list of $N$ elements of $[R]$ is almost never surjective, and it takes a coordinated flip to change that.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - 2^{-\Theta(n/\log n)}\) $\mathrm{Stab}_\rho=1-2\,\mathrm{NS}_\delta$ at $\rho=1-2\delta$ in the $\pm1$ normalisation, and $\mathrm{NS}_\delta=2^{-\Theta(n/\log n)}$. Surjectivity is a near-constant function on the uniform measure, so it is as stable as a constant to within its tiny bias.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Omega(n/\log n),\ O(n)\) $\mathrm{UC}^b\ge\mathrm{C}^b$ on each side, so $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=\Theta(n/\log n)$, and $\mathrm{UC}_{\min}\le\mathrm{UC}=\Theta(n)$. Which side is cheaper is exactly the open part: the $0$-certificates are the short ones. BHT17
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\tilde\Omega(n^{3/4}),\ O(n)\) $\widetilde{\deg}_\varepsilon\le\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg}=\tilde\Theta(n^{3/4})$ [BKT18] and $\mathrm{R}=\Theta(n)$. Closing this would settle whether the conical junta relaxation sees the $n^{3/4}$ barrier or the true randomized cost.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\tilde\Omega(\sqrt n),\ \tilde O(n^{3/4})\) $\mathrm{sdeg}\le\widetilde{\deg}_+\le\widetilde{\deg}$ (\(\widetilde{\deg}_{+}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{sdeg}(f)\) vs \(\widetilde{\deg}_{+}(f)\)), and the two ends are the recorded $\mathrm{sdeg}=\tilde\Theta(\sqrt n)$ and $\widetilde{\deg}=\tilde\Theta(n^{3/4})$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\tilde\Omega(\sqrt n),\ \tilde O(n^{3/4})\) putative Upper: $\mathrm{rdeg}_\varepsilon\le\widetilde{\deg}_\varepsilon$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)). Lower: if $p/q$ approximates $f$ to $1/3$ with $q>0$, then $p-q/2$ has the sign of $f-1/2$ everywhere, so $\mathrm{sdeg}\le\mathrm{rdeg}_{1/3}$; and $\mathrm{sdeg}=\tilde\Theta(\sqrt n)$. MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\tilde\Omega(\sqrt n),\ \tilde O(n^{3/4})\) $\mathrm{PostQ}_\varepsilon(f)=\Theta(\mathrm{rdeg}_\varepsilon(f))$ [MahadevdeWolf15], and the \(\mathrm{rdeg}_{\varepsilon}(f)\) entry places approximate rational degree between $\tilde\Omega(\sqrt n)$ and $\tilde O(n^{3/4})$. MahadevdeWolf15
\(\mathrm{rdeg}(f)\) Rational degree \(\Omega(n/\log n),\ O(n)\) putative $\mathrm{rdeg}(f)=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}\le\mathrm{C}(f)=\Theta(n)$. For the lower end, restrict as in \(\deg_2(f)\) but also fix all but one bit of each free slot to $1$: the restriction of $\bar f$ is $\mathrm{NOR}_{R+1}$, and a polynomial nonzero exactly at $0^t$ must be a multiple of $\prod_i(1-y_i)$, so $\mathrm{ndeg}(\bar f)\ge R+1=\Theta(n/\log n)$. deWolf03

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

Notes

In the element-query model, where one query returns a whole $x_i \in [R]$, the quantum bound is clean: $\mathrm{Q}(\mathrm{SURJ}_{N,N/2+1}) = \Theta(N)$ [BeameMachmouchi12, Cor. 2]. The tildes above are an artefact of the binary encoding.