Q The Query Complexity Zoo
\(\mathrm{THR}^n_k\)

Threshold

The whole one-parameter family interpolating OR ($k=1$), MAJ ($k=n/2$) and AND ($k=n$).

total basic arity: $n$ bits

Description

$\mathrm{THR}^n_k(x)=1$ iff $|x|\ge k$.

Formal definition

$\mathrm{THR}^n_k(x) = \mathbb{1}[\,\sum_{i=1}^n x_i \ge k\,]$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(n\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) Paturi92
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) BBCMdW01 NayakWu99
\(\mathrm{s}(f)\) Sensitivity \(\max\{k,\; n-k+1\}\)
\(\mathrm{bs}(f)\) Block sensitivity \(\max\{k,\; n-k+1\}\)
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n-k+1\)
\(\mathrm{C}^1(f)\) 1-certificate complexity \(k\)
\(\mathrm{sdeg}(f)\) Sign degree \(1\)
\(\mathrm{s}^0(f)\) 0-sensitivity \(n-k+1\) At an input with $k-1$ ones every zero is sensitive.
\(\mathrm{s}^1(f)\) 1-sensitivity \(k\) At an input with exactly $k$ ones every one is sensitive.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(n-k+1\)
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(k\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\max\{k,\;n-k+1\}\) Between $\mathrm{bs}$ and $\mathrm{C}$, which coincide here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\max\{k,\;n-k+1\}\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{C}(f)\) Certificate complexity \(\max\{k,\;n-k+1\}\)
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(\sqrt k)\) putative Only the $0$-side is constrained, and it is the interval $\{0,\dots,k-1\}$: Chebyshev on $k$ points gives $O(\sqrt k)$ and Markov gives $\Omega(\sqrt k)$. Compare $\widetilde{\deg} = \Theta(\sqrt{k(n-k+1)})$ -- one-sidedness removes the whole $n-k+1$ factor.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\)
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(\max\{k,\;n-k+1\})\) Sandwiched: $\mathrm{FC}(f) \le \mathrm{RC}(f) \le \mathrm{fbs}(f)$, with both ends $\max\{k,\;n-k+1\}$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(\max\{k,\;n-k+1\})\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \max\{k,\;n-k+1\}$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(\max\{k,\;n-k+1\})\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \max\{k,\;n-k+1\}$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(\max\{k,\;n-k+1\})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(\max\{k,\;n-k+1\})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) $\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) = \Theta\!\big(\sqrt{k(n-k+1)}\big)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) $\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) = \Theta\!\big(\sqrt{k(n-k+1)}\big)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta\!\big(\sqrt{k(n-k+1)}\big)$ here.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\min\{k,\; n-k+1\}\) putative A $1$-input needs $k$ ones exhibited and a $0$-input needs $n-k+1$ zeros, so $\mathrm{C}(x)$ takes exactly the two values $k$ and $n-k+1$; the minimum over inputs is the smaller of them. Contrast $\mathrm{C} = \max\{k,\;n-k+1\}$: the gap between \(\mathrm{C}_{\min}(f)\) and \(\mathrm{C}(f)\) on this one family is already unbounded (take $k=1$).
\(\deg(f)\) Exact degree \(n\) putative The top Fourier coefficient is $\sum_{j\ge k}(-1)^{n-j}\binom{n}{j} = (-1)^{n-k}\binom{n-1}{k-1} \ne 0$, so the multilinear polynomial has the full monomial $x_1\cdots x_n$ for every $1 \le k \le n$. This is the tight end of the von zur Gathen-Roche bound recorded on \(f = f(|x|)\).
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) Between $\deg(f)/2 = n/2$ and the trivial $n$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) Between $\mathrm{rdeg}(f)/2 = \max\{k,\,n-k+1\}/2 \ge (n+1)/4$ and $\mathrm{Q}_{E}(f) \le n$. (The $\deg/2$ floor would be a $\mathrm{Q}_{\mathrm{E}}$ bound; here $\mathrm{rdeg}$ happens to be $\Theta(n)$ for every $k$, so $\mathrm{Q}_0$ is pinned anyway -- even where $\mathrm{Q} = \Theta(\sqrt{k(n-k+1)})$ is much smaller.)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) $\mathrm{R}(f) = \Omega(\mathrm{bs}(f)) = \Omega(\max\{k,\;n-k+1\}) = \Omega(n)$. Note this holds uniformly in $k$, unlike $\mathrm{Q}$, which drops to $\Theta(\sqrt n)$ at the two ends.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\)
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\)
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\)
\(\mathrm{I}(f)\) Total influence (L2 influence) \(n\binom{n-1}{k-1}2^{1-n}\) putative Coordinate $i$ is pivotal exactly when the other $n-1$ bits have weight $k-1$. At $k = n/2$ this is $\Theta(\sqrt n)$, recovering \(\mathrm{MAJ}_n\); at $k=1$ it is $n2^{1-n}$, recovering \(\mathrm{OR}_n\).
\(\mathrm{MaxInf}(f)\) Maximum influence \(\binom{n-1}{k-1}2^{1-n}\) putative The family is transitive, so every coordinate carries the same influence: $\mathrm{Inf}(f)/n$.
\(\mathrm{Var}(f)\) Variance \(4p(1-p),\quad p = 2^{-n}\sum_{j\ge k}\binom nj\) The whole family in one line; $p\to\tfrac12$ and $\mathrm{Var}\to 1$ for $k$ within $O(\sqrt n)$ of $n/2$, and $\mathrm{Var}$ is exponentially small at the extremes $k \in \{1,n\}$, where the threshold degenerates to \(\mathrm{OR}_n\) and \(\mathrm{AND}_n\).
\(\mathrm{I}^{1}(f)\) Total L1 influence \(n\binom{n-1}{k-1}2^{1-n}\) putative For a Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, so this is the recorded $\mathrm{I}(f)$ verbatim.
\(\lambda(f)\) Spectral sensitivity \(\sqrt{k(n-k+1)}\) putative The sensitivity graph is exactly the bipartite graph between Hamming layers $k-1$ and $k$ of the cube: it is biregular of degrees $n-k+1$ (from the $k-1$ side) and $k$ (from the $k$ side), and a connected biregular bipartite graph has spectral norm $\sqrt{d_0 d_1}$ -- put $a$ on one side and $b$ on the other, so that $(n-k+1)b = \lambda a$ and $ka = \lambda b$. Recovers $\lambda(\mathrm{MAJ}) = (n+1)/2$ and $\lambda(\mathrm{OR}) = \sqrt n$, and it is exactly $\sqrt{\mathrm{C}^0\mathrm{C}^1}$, so [Huang19]'s $\deg \le \lambda^2$ is tight here only at the two ends.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) putative Lower: Ambainis' unweighted adversary with $A$ the weight-$(k-1)$ inputs, $B$ the weight-$k$ inputs and Hamming distance $1$ gives $m = n-k+1$, $m' = k$, $\ell = \ell' = 1$ and hence $\sqrt{mm'/\ell\ell'} = \sqrt{k(n-k+1)}$. Upper: $\mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, which is the same quantity. So the positive-weight adversary is already tight on the whole threshold family -- the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1}$ is met with equality. Ambainis02
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(k\) putative Upper: $\prod_{j=0}^{k-1}(|x|-j)$ is nonzero exactly on the $1$-inputs and has degree $k$. Lower: let $S$ be a minimal set in the Fourier-style monomial support of a witnessing multilinear $p$; then $p(1_S) = \sum_{T \subseteq S} c_T = c_S \ne 0$, so $1_S$ is a $1$-input and $|S| \ge k$. Dually $\mathrm{ndeg}(\bar f) = n-k+1$.
\(\mathrm{rdeg}(f)\) Rational degree \(\max\{k,\;n-k+1\}\) putative Exactly, from the characterisation $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\} = \max\{k,\,n-k+1\}$ using the \(\mathrm{ndeg}(f)\) line above. Consistent with the two general bounds $\mathrm{rdeg} \le \mathrm{C} = \max\{k,\,n-k+1\}$ and $\mathrm{rdeg} = \Omega(\deg)$ for symmetric $f$ [IJKKKSWW23], which here pin it from both sides. IJKKKSWW23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(k)\) putative Exactly $\lceil k/2 \rceil$, by de Wolf's $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg} = k$. Note this is not below $\mathrm{Q}$: at $k = n$ (\(\mathrm{AND}_n\)) nondeterministic quantum costs $n/2$ while bounded-error quantum costs $\Theta(\sqrt n)$, because the nondeterministic model is one-sided. deWolf00
\(\mathrm{rank}(f)\) Decision tree rank \(\min\{k,\; n-k+1\}\) putative Prover--Delayer: if the Delayer always defers, the Prover must drive the transcript to $k$ ones or to $n-k+1$ zeros before the value is fixed, and scores nothing on the way, so the Delayer banks $\min\{k,\,n-k+1\}$ points. Conversely $r(n,k) := \min\{k,\,n-k+1\}$ satisfies the rank recursion for the tree that queries $x_1$ first: its children have ranks $r(n-1,k-1)$ and $r(n-1,k)$, which differ by one when $k \ne n-k+1$ and are equal to $r(n,k)-1$ when $k = n-k+1$. Recovers $\mathrm{rank}(\mathrm{OR}) = 1$ and $\mathrm{rank}(\mathrm{MAJ}) = (n+1)/2$; against $\mathrm{D} = n$ this is an unbounded rank-vs-depth gap already inside the threshold family.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\max\{k,\;n-k+1\}\) Squeezed: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, and both ends are $\max\{k,\,n-k+1\}$ here. GJKKLSSV17
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) Squeezed: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = \max\{k,\,n-k+1\} \ge (n+1)/2$ and $\mathrm{D}(f) = n$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) putative Immediately from $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f)-1$ [BHT17] with $\mathrm{fbs} = \max\{k,\,n-k+1\}$, together with $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. A self-contained route gives the same bound with better constants. Unambiguous covers restrict: intersecting each subcube of a cover with a subcube $\rho$ leaves an unambiguous cover of $f|_\rho$ of no larger width, so $\mathrm{UC}^b(f|_\rho) \le \mathrm{UC}^b(f)$. Fixing $k-1$ ones turns $\mathrm{THR}^n_k$ into $\mathrm{OR}_{n-k+1}$ and fixing $n-k$ zeros turns it into $\mathrm{AND}_k$; for both of these each side has an odd number of inputs ($2^m-1$, or the single point), so some subcube of any unambiguous cover has full codimension. Hence $\mathrm{UC}^0, \mathrm{UC}^1 \ge \max\{k,\,n-k+1\}$ and $\mathrm{UC}_{\min} = \Theta(n)$ -- the threshold family cannot witness anything for the [BHT17] $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ question. BHT17
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) Squeezed: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) \ge (n+1)/2$ and $\mathrm{D}(f) = n$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Squeezed: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) Squeezed: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$. BenDavidKothari18
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Squeezed: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Squeezed: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Squeezed: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$. BBGM22
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Squeezed: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$. BBGM22
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. Fractional queries buy nothing at the top of the range. CKMPSS23
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Squeezed: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{s}(f) = \max\{k,\,n-k+1\}$ and $\mathrm{D}(f) = n$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Squeezed: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{s}(f) = \max\{k,\,n-k+1\}$ and $\mathrm{D}(f) = n$. 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.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(\max\{k,\,n-k+1\}) = \Theta(n)$ here. Verifying a threshold is quadratically cheaper than computing it, uniformly in $k$. Aaronson08
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(k(n-k+1))\) Squeezed by the [CGLMSG23] sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$: the upper end is $k(n-k+1)$ and $\mathrm{Adv}^2 = \Theta(k(n-k+1))$ from the \(\mathrm{Adv}(f)\) line above. Interpolates the two recorded endpoints, $\Theta(n)$ for \(\mathrm{OR}_n\) and $\Theta(n^2)$ for \(\mathrm{MAJ}_n\), and shows the whole intermediate range $n^{1+c}$ is realised. CGLMSG23
\(\deg_2(f)\) Mod-2 degree \(\Theta(n)\) putative Over $\mathbb{F}_2$, $\mathrm{THR}^n_k = \sum_{|S|\ge k}\binom{|S|-1}{k-1}\prod_{i\in S}x_i$, so $\deg_2 = \max\{s \le n : \binom{s-1}{k-1} \text{ odd}\}$, which by Lucas is the largest $s-1 \le n-1$ whose binary expansion contains that of $k-1$. Let $2^t \le n-1 < 2^{t+1}$. If $k-1 < 2^t$ then $s-1 = 2^t-1$ qualifies and $\deg_2 \ge 2^t \ge (n-1)/2$; otherwise $k-1 \ge 2^t$ and already $s-1 = k-1$ gives $\deg_2 \ge k > (n-1)/2$. So thresholds get at most a factor-two discount from characteristic $2$; see the exact $\deg_2(\mathrm{MAJ}_n) = 2^{\lfloor\log_2 n\rfloor}$ on \(\mathrm{MAJ}_n\).
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(n\) putative Every singleton is in the Fourier support: $\hat f(\{i\})$ is a nonzero multiple of $\binom{n-1}{k-1}$, which is exactly the statement that $\mathrm{MaxInf}(f) \ne 0$. The $n$ singletons already span $\mathbb{F}_2^n$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) putative Take the product distribution with each bit $1$ independently with probability $p$ chosen so that $\Pr[|x| \ge k] = \tfrac12$; this is $p = \Theta(k/n)$. Run a depth-$m$ deterministic tree and follow the single path on which every answer is $0$: it is reached with probability $(1-p)^{m}$, and conditioned on it the residual weight is $\mathrm{Bin}(n-m,p)$, whose chance of reaching $k$ stays bounded away from $0$ and $1$ as long as $m \le \alpha n$ for a small constant $\alpha$. The product of the two is more than $1/3$, so $\mathrm{D}^{\mathrm{prod}} = \Omega(n)$, matching the trivial $\mathrm{D} = n$. Even at $k=1$, where the threshold sits at the very edge, no product distribution is easy.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(\log n)\) Newman's degree-$O(\log(1/\delta))$ rational approximation to $\mathrm{sign}$ on $[-1,-\delta]\cup[\delta,1]$, applied after the affine map $j \mapsto (j-k+\tfrac12)/n$ so that $\delta = \Theta(1/n)$. Recorded as an upper bound only, because the truth genuinely depends on $k$: it is $\Theta(\log n)$ at $k = n/2$ [MahadevdeWolf15] but only $1$ at $k=1$, where $2|x|/(1+2|x|)$ already separates $|x|=0$ from $|x|\ge1$. Newman64 MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(\log n)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$, and the \(\mathrm{rdeg}_{\varepsilon}(f)\) line above gives $O(\log n)$. Postselection collapses the whole threshold family to polylogarithmic cost, against $\mathrm{Q} = \Theta(\sqrt{k(n-k+1)})$. MahadevdeWolf15
\(\mathrm{DTsize}(f)\) Decision tree size \(O\!\big(\binom{n+1}{k}\big)\) putative The counting tree, which reads $x_1,x_2,\dots$ and stops as soon as $k$ ones or $n-k+1$ zeros have been seen, has $\sum_{z\le n-k}\binom{k-1+z}{z} + \sum_{o<k}\binom{n-k+o}{o} = \binom{n}{k}+\binom{n}{k-1} = \binom{n+1}{k}$ leaves by the hockey-stick identity. Upper bound only: the best easy lower bound is $2^{\min\{k,\,n-k+1\}}$, from the fact that every leaf subcube has codimension at least $\min\{k,\,n-k+1\}$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$, uniformly in $k$ by the \(\mathrm{R}_{\varepsilon}(f)\) line, and the \(\mathrm{D}^{\mathrm{prod}}(f)\) line exhibits a product distribution attaining it. Yao77
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\max\{k,\; n-k+1\}\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, recorded on the \(\mathrm{bs}(f)\) line. GoosPitassi14
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$, uniformly in $k$. CDM23
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(n)\)· putative Restricting $k-1$ variables to $1$ turns $\mathrm{THR}^n_k$ into $\vee_{n-k+1}$, and restricting $n-k$ variables to $0$ turns it into $\wedge_k$. A conical junta restricts to a conical junta of no larger width, so the \(\mathrm{OR}_n\) and \(\mathrm{AND}_n\) lower bounds give $\mathrm{cjdeg} = \Omega(\max\{k,\ n-k+1\}) = \Omega(n)$; and $\mathrm{cjdeg}_{\varepsilon} \le \mathrm{D} = n$. So, uniformly in $k$, non-negativity destroys the $\widetilde{\deg} = \Theta(\sqrt{k(n-k+1)})$ saving -- at $k=1$ this is a quadratic gap.
\(\deg_p(f)\) Mod-p degree \(\Theta(n)\) putative For every prime $p$. Over the integers $\mathrm{THR}^n_k = \sum_{|S| \ge k} (-1)^{|S|-k}\binom{|S|-1}{k-1}\prod_{i \in S} x_i$ (the \(\deg(f)\) line), and reducing this unique multilinear form mod $p$ shows $\deg_p = \max\{s \le n : \binom{s-1}{k-1} \not\equiv 0 \bmod p\}$. Taking $s = k$ gives the coefficient $\binom{k-1}{k-1} = 1$, so $\deg_p \ge k$; substituting $x_i \mapsto 1-x_i$ preserves degree and maps $\mathrm{THR}^n_k$ to the complement of $\mathrm{THR}^n_{n-k+1}$, so also $\deg_p \ge n-k+1$. Hence $\deg_p \ge \max\{k,\ n-k+1\} \ge (n+1)/2$, and $\deg_p \le n$. No prime helps, in contrast with \(\mathrm{ADDR}_k\).
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(n)\) putative Between $n - \log_2 n$ and $n$. Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. Lower by granularity: in the $\pm1$ encoding the top Fourier coefficient is $\pm 2^{1-n}\binom{n-1}{k-1}$ (the \(\deg(f)\) line), so the granularity is at least $n-1-\nu_2\binom{n-1}{k-1}$, and $\mathrm{D}^{\oplus} \ge \mathrm{gran}+1$ [ChistopolskayaPodolskii18]. By Kummer's theorem $\nu_2\binom{n-1}{k-1}$ counts the carries when adding $k-1$ and $n-k$ in base $2$, hence is at most $\log_2 n$. At $k = (n+1)/2$ this reproduces the exact $n - \mathrm{B}(n) + 1$ recorded for \(\mathrm{MAJ}_n\); parity queries never help a threshold. ChistopolskayaPodolskii18
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(n),\ O(n\log n)\)· Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$, uniformly in $k$. Upper: $O(\mathrm{R}\log\mathrm{R})$ by repeating each query $O(\log n)$ times. Recorded as a range because the truth genuinely depends on $k$: the log factor is needed at $k = (n+1)/2$ (\(\mathrm{MAJ}_n\), $\Theta(n\log n)$) and is not needed at $k = 1$ (\(\mathrm{OR}_n\), $\Theta(n)$). The influence-based bound $\mathrm{N}_p = \Omega(\mathrm{I}\log\mathrm{I})$ [GLX26noisy] with $\mathrm{I} = n\binom{n-1}{k-1}2^{1-n}$ interpolates between the two. FRPU94 GLX26noisy
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) Theorem 4 of [BNRdW05] gives a robust quantum algorithm using $O(\sqrt{n(n-\Gamma(f)+1)})$ queries for every symmetric $f$; here $\Gamma = |2k-n-1|$, so $n - \Gamma + 1$ is $2k$ for $k \le (n+1)/2$ and $2(n-k+1)$ otherwise, and the bound reads $O(\sqrt{k(n-k+1)})$. That matches $\mathrm{Q}$ from above, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$. So noise is free for the quantum algorithm at every $k$, while classically it costs a $\log$ factor at $k \approx n/2$. BNRdW05