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

Ordered search

Where quantum buys only a constant factor: $\mathrm{D} = \lceil\log_2(n+1)\rceil$ and $\mathrm{Q} = \Theta(\log n)$, with the constant pinned between $0.221$ and $0.390$.

partial separating arity: $n$ bits under the promise $x_1 \le x_2 \le \cdots \le x_n$— also: binary search, insertion into a sorted list

Description

Promise: $x = 0^k1^{\,n-k}$ for some $0 \le k \le n$. The reconstruction version outputs $k$; the decision version outputs $\mathrm{parity}(k)$, which is the Boolean form the degree measures need. Equivalently: insert an item into a sorted list of $n$ items using comparisons.

Together with \(\mathrm{SEARCH}_n\) this is one of the two calibration points for $\mathrm{R}$ versus $\mathrm{Q}$ -- the one where the answer is "nothing much".

Formal definition

$\mathrm{OS}_n(0^k1^{n-k}) = k$ on the promise; the decision version is $\mathrm{OS}^{\oplus}_n(0^k1^{n-k}) = k \bmod 2$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(\lceil \log_2(n+1) \rceil\) Exactly. Upper: binary search. Lower: a depth-$T$ tree has at most $2^T$ leaves and must separate all $n+1$ promise inputs.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\log_2 n - \Theta(1)\) Randomness buys a constant number of queries, not a constant factor. Upper: $\mathrm{R}\le\mathrm{D}$. Lower, by Yao plus leaf-counting: under the uniform distribution on the $n+1$ inputs a $T$-query deterministic tree is right on at most $2^T$ of them, so success $\ge 2/3$ forces $T \ge \log_2(n+1) - \log_2(3/2)$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\log_2 n \pm \Theta(1)\) Sandwiched: $\mathrm{R} \le \mathrm{R}_0 \le \mathrm{D}$, and both ends are $\log_2 n \pm O(1)$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\log n)\) The constant is open. Lower: $\tfrac1\pi(\ln n - 1) \approx 0.2206\log_2 n$ [HNS02], by a weighted all-pairs inner-product argument. Upper: $5\log_{7265} n \approx 0.390\log_2 n$ [CCKS25]. The ladder of lower bounds: $\Omega(\sqrt{\log n}/\log\log n)$ [BuhrmandeWolf99ordered], $\log_2 n/(2\log\log n)$ [FGGS98limit], $\tfrac1{12}\log_2 n$ [Ambainis99ordered], then HNS. HNS02 CCKS25
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(\log n)\) Upper $0.390\log_2 n$: [CCKS25] show every bounded-error $k$-query algorithm can be made translation-invariant with no workspace, and an LP search then finds an exact $5$-query algorithm for lists of length $7265$. Earlier exact algorithms: $0.526\log_2 n$ ($3$ queries, $52$ items) [FGGS99invariant], $0.433\log_2 n$ ($4$ queries, $605$ items) [CLP07]. Lower: $\mathrm{Q}_E \ge \mathrm{Q} \ge \tfrac1\pi(\ln n - 1)$. CCKS25 HNS02
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(1)\) putative Decision version, like the rest of the combinatorial column here. The certificate barrier applies: two queries $\{x_k = 0,\ x_{k+1} = 1\}$ pin the boundary, so $\mathrm{C}^0 = \mathrm{C}^1 = 2$ and $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 2$. Against $\mathrm{Adv}^{\pm} = \widetilde\Theta(\log n)$ this is one of the cleanest positive-vs-negative-weight gaps in the zoo, and it is not the usual property-testing shape -- the promise is as far from a testing promise as it gets. For the $(n+1)$-valued reconstruction version the picture inverts: [ChildsLee08] compute the exact optimum of the adversary bound as $\tfrac1\pi\ln n + O(1)$, matching Hoyer-Neerbek-Shi, so the method is optimal there. The barrier is a theorem about Boolean output and does not survive the larger alphabet -- see \(\mathrm{Adv}(f)\) vs \(\mathrm{C}(f)\). ChildsLee08 SpalekSzegedy06
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\tfrac1\pi\ln n + O(1)\) The same ceiling holds for negative weights, so improving $0.221\log_2 n$ needs a genuinely different technique. Unlike the positive-weight $\mathrm{Adv}$ above, this survives the passage to the Boolean decision version, since $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$ and $\mathrm{Q}$ is $\widetilde\Theta(\log n)$ either way. ChildsLee08
\(\mathrm{C}(f)\) Certificate complexity \(2\) putative Decision version, $n \ge 2$: $\{x_k = 0,\ x_{k+1} = 1\}$ pins $k$ and hence the answer, and one query cannot. This is what makes the positive adversary useless here.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(2\) putative Same two-query certificate; the promise makes both sides equally cheap to certify.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(2\) putative Same two-query certificate; the promise makes both sides equally cheap to certify.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(1\) putative At the two extreme inputs $0^n$ and $1^n$ a single query at the relevant end suffices, since only one promise input is consistent with it.
\(\deg(f)\) Exact degree \(1\) putative Under the zoo's partial-function convention -- agree with $f$ on the domain, unconstrained off it -- the promise makes $x_j = [\,j \ge k\,]$, so for any target $g(k)$ the degree-one polynomial $p(x) = g(0) + \sum_j (g(j+1)-g(j))(1 - x_j)$ is exactly right. Hence $\deg = 1$ for every Boolean predicate of $k$, and the unbounded polynomial method says nothing here. [BunVoronova23] write "degree $n$" for the same object; they mean a bounded polynomial.
\(\mathrm{sdeg}(f)\) Sign degree \(1\) From $\mathrm{sdeg} \le \deg = 1$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(1\) Squeezed between $\mathrm{sdeg} = 1$ and $\deg = 1$. Like $\deg$ and $\mathrm{sdeg}$, and unlike $\widetilde{\deg}$, the one-sided approximate degree is blind to the promise: it never asks the polynomial to stay bounded off the domain.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) Decision version. [BunVoronova23, Def. 5, Thm. 12]: $\widetilde{\deg}_{1/2-\gamma}(\mathrm{OS}^{\oplus}_{2^m}) = \Omega(m/\log^2 m - \log(1/\gamma))$, which in the number of input variables $n = 2^m$ is the bound stated. Upper: binary search. Previous best was $\Omega(\sqrt{\log n})$ [BuhrmandeWolf99ordered]. The whole distance between this and $\deg = 1$ is the boundedness requirement off the promise. BunVoronova23
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(\log n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{Q}_{\mathrm{E}}(f)$, with both ends $\Theta(\log n)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\log n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\mathrm{E}}(f)$, with both ends $\Theta(\log n)$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(\log 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) = \log_2 n - \Theta(1)$ here. The expected-cost version does not beat binary search by more than a constant, unlike the quantum case.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(\log n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$, and the maximising $\mu$ is the uniform distribution on the $n+1$ promise inputs -- which is exactly the distribution the $\mathrm{R}$ entry's leaf-counting argument uses.
\(\mathrm{rank}(f)\) Decision tree rank \(1\) putative The cheapest illustration in the zoo of rank ignoring caterpillars. Linear search -- query $x_1$; if it is $1$ output $k=0$, otherwise query $x_2$, and so on -- is a comb: every internal node has a leaf for one child, so the rank never rises above $1$, while the depth is $n$. Hence $\mathrm{rank} = 1$ against $\mathrm{D} = \lceil\log_2(n+1)\rceil$: the size-optimal and depth-optimal trees are different trees, and the rank-optimal one is neither. ($\mathrm{rank} \ge 1$ because $\mathrm{OS}_n$ is not constant.)
\(\mathrm{DTsize}(f)\) Decision tree size \(n+1\) putative Exactly. Lower: the promise inputs reaching a fixed leaf are those $k$ compatible with the answers along the path, which is an interval of $k$; consecutive $k$ have opposite parity, so on the decision version $\mathrm{OS}^{\oplus}_n$ that interval must be a singleton, and there are $n+1$ inputs. Upper: binary search has exactly $n+1$ leaves. Consistent with the Ehrenfeucht-Haussler bound: a rank-$1$ tree of depth $n$ has at most $n+1$ leaves, and the comb attains it.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) putative A fixed query set $S$ tells you only which gap of $S$ the boundary $k$ falls into, i.e. an interval of candidate $k$; the $|S|+1$ intervals must all be singletons to determine the parity, and there are $n+1$ candidates, so $|S| \ge n$. Adaptivity is worth an exponential factor here -- the largest possible, since $\mathrm{D}^{\mathrm{na}} \le n$ always.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) putative Randomness does not rescue non-adaptivity. Take $k$ uniform on $\{0,\dots,n\}$; a fixed query set of size $t$ leaves the parity determined only when the gap containing $k$ is a singleton, and there are at most $t+1$ singleton gaps, so the algorithm is right with probability at most $\tfrac{t+1}{n+1} + \tfrac12\big(1-\tfrac{t+1}{n+1}\big)$. Forcing this to $\ge 2/3$ gives $t \ge \tfrac{n+1}{3}-1$. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = n$.
\(\mathrm{s}(f)\) Sensitivity \(2\) putative Decision version, $n \ge 2$. Flipping bit $j$ of $0^k1^{n-k}$ leaves the promise unless $j \in \{k, k+1\}$, and those two flips move to $k-1$ and $k+1$, both of which change the parity. So $\mathrm{s}_x = 2$ in the interior and $1$ at $k \in \{0,n\}$. This is the measure's partial-setting warning made concrete: $\mathrm{s} = 2$ while $\mathrm{R} = \Theta(\log n)$. The certificate family is $\Theta(1)$ too -- $\{x_k = 0,\,x_{k+1} = 1\}$ pins $k$ among promise inputs, so $\mathrm{C} = \mathrm{C}^0 = \mathrm{C}^1 = 2$ and $\mathrm{C}_{\min} = 1$ -- but those cells are deliberately left blank, because the zoo's \(\mathrm{Adv}(f)\) vs \(\mathrm{C}(f)\) record (the certificate-complexity barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1}$) is a theorem about partial Boolean functions, whereas the $\mathrm{Adv}$ value recorded below is [ChildsLee08]'s exact bound for the $(n+1)$-valued search version. Those two coexisting -- $\mathrm{Adv} = \tfrac1\pi\ln n$ against $\mathrm{C} = 2$ -- is precisely the observation that the barrier does not survive a large output alphabet; on the Boolean version $\mathrm{OS}^{\oplus}_n$ the barrier does apply and forces $\mathrm{Adv} = O(1)$ despite $\mathrm{Q} = \tilde\Theta(\log n)$, which is why [BunVoronova23] had to go through approximate degree.
\(\mathrm{s}^0(f)\) 0-sensitivity \(2\) putative Attained at any interior $k$ of even parity, $n \ge 3$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(2\) putative Attained at any interior $k$ of odd parity, $n \ge 3$.
\(\mathrm{bs}(f)\) Block sensitivity \(2\) putative Decision version. Flipping a block $B$ of $0^k1^{n-k}$ stays on the promise only if $B$ is the interval between the old and the new boundary, so every sensitive block contains position $k$ (if it moves the boundary down) or position $k+1$ (if it moves it up). Two disjoint sensitive blocks are therefore the most possible, and $k\pm1$ supplies them.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(2\) putative Same argument as $\mathrm{bs}$, at an interior $k$ of even parity.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(2\) putative Same argument as $\mathrm{bs}$, at an interior $k$ of odd parity.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(2\) putative Every "down" block contains position $k$ and every "up" block contains position $k+1$, so the two load constraints alone cap the LP at $2$, which the two unit blocks attain. No fractional gain over $\mathrm{bs}$ here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(2\) putative Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(1)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = 2$.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(2\) putative Query positions $k$ and $k+1$ and reject unless the answers are $0$ and $1$: any promise input with a different boundary fails one of the two checks with certainty. $\mathrm{RC} \ge \mathrm{bs} = 2$, and Aaronson's $\mathrm{RC} = \Theta(\mathrm{fbs})$ agrees.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(\log n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(\log n)$ here.
\(\lambda(f)\) Spectral sensitivity \(\Theta(1)\) putative Exactly $2\cos\!\big(\tfrac{\pi}{n+2}\big)$, which climbs to $2$ and never reaches it -- a constant, and that is the whole content: the sensitivity graph is a path. Its vertices are the $n+1$ promise inputs $0^k1^{n-k}$; two of them are Hamming neighbours exactly when their indices differ by one, and then the answers differ too, so $G_f = P_{n+1}$, whose adjacency matrix has spectral norm $2\cos(\pi/(n+2)) < 2$. Against $\mathrm{Q} = \Theta(\log n)$ this is the sharpest cheap illustration that spectral sensitivity is worthless on a promise: $\mathrm{Q} = \Omega(\lambda)$ gives nothing, and Huang's $\deg \le \lambda^2$ is vacuous here because $\deg = 1$ as well.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\log 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} = \Theta(\log n)$ here. Note the contrast with the positive-weights $\mathrm{Adv} = \Theta(1)$ on this page: the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 2$ bites, and only the general adversary escapes it.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(\log n)\) Between $\mathrm{R} = \log_2 n - \Theta(1)$ and $O(\mathrm{R}\log \mathrm{R}) = O(\log n\log\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Whether the $\log\log n$ is real is the noisy-binary-search question of Feige-Raghavan-Peleg-Upfal.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\tilde\Theta(\log n)\) Between $\mathrm{Q} = \Theta(\log n)$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(\log n\log\log n)$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)).
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) Squeezed between $\widetilde{\deg}$ and $\mathrm{R}_{\varepsilon}$, so it inherits the [BunVoronova23] window exactly. Worth contrasting with $\deg = 1$: imposing non-negativity on top of boundedness changes nothing further here, but dropping boundedness collapses the measure completely.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(1\) putative One parity query. On the promise $x=0^k1^{n-k}$ the decision version is $\mathrm{OS}^{\oplus}=k\bmod 2=(n\bmod 2)\oplus\bigoplus_i x_i$, so the single query $\bigoplus_{i\in[n]}x_i$ settles it, against $\mathrm{D}=\lceil\log_2(n+1)\rceil$. The same identity is why $\deg=1$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(1\) putative The support of a product measure is a subcube, and a subcube inside the promise has dimension at most $1$: a $2$-dimensional subcube contains two inputs of equal Hamming weight, and the chain has none. A $1$-dimensional one is a pair $x^{(k)},x^{(k+1)}$ differing in coordinate $k+1$, which one query settles, and the balanced such measure needs that query. So $\mathrm{D}^{\mathrm{prod}}=1$ while $\mathrm{R}=\Theta(\log n)$ -- product distributions are useless on a chain promise.
\(\deg_p(f)\) Mod-p degree \(1\) putative Same construction as the $\deg=1$ entry, over $\mathbb{F}_p$: with $p(x)=\sum_i c_ix_i$ one has $p(x^{(k)})=\sum_{i>k}c_i$, and choosing $c_i=\pm1$ alternating makes the partial sums alternate between $0$ and $1$, which is $k\bmod 2$ on the promise.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(1\) putative A linear form suffices: pick $c_i$ so that $\sum_{i>k}c_i$ is $0$ for even $k$ and $1$ for odd $k$ (successive differences are $\pm1$), giving $p$ nonzero exactly on the $1$-inputs of the promise. Nondeterministic degree is defined on the domain only, so nothing off the chain constrains $p$; and $\mathrm{ndeg}\ge1$ since the function is nonconstant.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(1\) $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil$ [deWolf03] and $\mathrm{ndeg}=1$. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(1\) $\mathrm{rdeg}=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$ [deWolf03], and both sides are $1$ by the \(\mathrm{ndeg}(f)\) argument applied to $f$ and to its complement (shift the alternating partial sums by one). deWolf03
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(1\) $1\le\mathrm{rdeg}_{1/3}\le\mathrm{rdeg}=1$. Note the contrast with $\widetilde{\deg}=\Omega(\log n/(\log\log n)^2)$: approximate degree demands boundedness off the promise, rational approximation does not.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)=\Theta(1)$ [MahadevdeWolf15]. Post-selection collapses ordered search: $\mathrm{Q}=\Theta(\log n)$ but a post-selected algorithm needs only a constant number of queries. MahadevdeWolf15
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(\log n)\) putative The fixed coordinates of a sabotaged input must still be $0$s before $1$s, so a $\ast$ that matters always lies in the gap between the last fixed $0$ and the first fixed $1$; binary search on that gap finds one in $\lceil\log_2 n\rceil$ queries. For the lower bound, the $n$ inputs $0^{i-1}\ast1^{n-i}$ each have a unique correct answer, so a tree needs $n$ leaves. BenDavidKothari18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(\log n)\) $\bar\chi=\Omega(\mathrm{RS})=\Omega(\log n)$ [GLSS19] with the \(\mathrm{RS}(f)\) entry, and $\bar\chi=O(\mathrm{LR})\le O(\mathrm{R})=O(\log n)$ (\(\bar{\chi}(f)\) vs \(\mathrm{LR}(f)\)). GLSS19
\(\chi(f)\) Conflict complexity \(O(\log n)\) $\chi\le\bar\chi=\Theta(\log n)$ (\(\chi(f)\) vs \(\bar{\chi}(f)\)). No lower bound: the route $\mathrm{R}=O(\chi^2)$ is recorded only for total functions.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(\log n)\) $\mathrm{LR}\le\mathrm{R}=O(\log n)$ [BBGM22], and $\bar\chi=O(\mathrm{LR})$ with $\bar\chi=\Theta(\log n)$ gives the matching lower bound. So the linearised measure does not see the $\sqrt{\mathrm{R}}$ slack here: ordered search composes perfectly. BBGM22 GLSS19
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) $\widetilde{\deg}_{2\varepsilon}\le\mathrm{prt}_\varepsilon+\log(1/\varepsilon)\le2\,\mathrm{R}_\varepsilon+\log(1/\varepsilon)$ [JainKlauck10], so the partition bound inherits the recorded approximate degree window between $\Omega(\log n/(\log\log n)^2)$ and $O(\log n)$. JainKlauck10 BunVoronova23
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) Same window as \(\mathrm{prt}_{\varepsilon}(f)\): $\widetilde{\deg}_{2\varepsilon}\le\overline{\mathrm{prt}}_\varepsilon+\log(1/\varepsilon)$ [KLLRX15] and $\overline{\mathrm{prt}}\le\mathrm{prt}\le2\,\mathrm{R}$. JainKlauck10 KLLRX15
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(O(\log n)\) $\mathrm{noisyR}\le\mathrm{R}=O(\log n)$ [BenDavidBlais20composition]. The strengthening "$\mathrm{R}=\Theta(\text{arity})\Rightarrow\mathrm{noisyR}=\Theta(\mathrm{R})$" does not apply: the arity is $n$, not $\log n$. Noisy binary search is the natural candidate for a matching lower bound, but the answer here is a single bit, so the information-per-cost argument gives only $\Omega(1)$. BenDavidBlais20composition
\(\mathrm{SP}(f)\) Subcube partition complexity \(2\) putative The $n+1$ subcubes $\{x_k=0,x_{k+1}=1\}$ (with $\{x_1=1\}$ and $\{x_n=0\}$ at the ends) have codimension at most $2$ and each meets the promise in exactly one input, so they partition $\mathrm{Dom}(f)$ into monochromatic pieces. And $\mathrm{SP}\ge\mathrm{C}=2$. A subcube partition of size $2$ against $\mathrm{D}=\Theta(\log n)$: the $\mathrm{D}$ versus $\mathrm{SP}$ question is hopeless on promises.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(2\) $\mathrm{UC}=\mathrm{SP}$ exactly, and the partition of the \(\mathrm{SP}(f)\) entry is already unambiguous on each side separately -- input $x^{(k)}$ is consistent with the certificate $\{x_k=0,x_{k+1}=1\}$ and with no other.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(2\) $\mathrm{UC}_{\min}=\min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ [BHT17], and both sides are $2$ by the family of the \(\mathrm{UC}(f)\) entry; the floor is $\mathrm{C}_{\min}$ on the relevant side. BHT17
\(\mathrm{EC}(f)\) Expectational certificate complexity \(O(\sqrt n)\)· putative Put $w^{x^{(k)}}_i=1/\sqrt{k+1-i}$ for $i\le k$ and $1/\sqrt{i-k}$ for $i>k$, so every weight is in $[0,1]$ and $\sum_iw^x_i\le4\sqrt n$. Two promise inputs $k$ and $k+d$ have different values only for odd $d$, and they differ exactly on the $d$ coordinates between them, where $\sum_{t=1}^{d}1/\sqrt{t(d+1-t)}\ge1$ (equality at $d=1$, tending to $\pi$). The certificate weighting is not available: the $d=1$ constraints force $w^{x^{(k)}}_k=w^{x^{(k)}}_{k+1}=1$, and supports two apart then fail to overlap. The total-function bound $\mathrm{EC}\le\mathrm{C}=2$ does not hold on a promise.
\(\mathrm{CA}(f)\) Classical adversary bound \(O(\log n)\) $(1-4\varepsilon)\mathrm{CA}\le\mathrm{prt}_\varepsilon+\log(1/\varepsilon)$ for partial functions [JainKlauck10, CGLMSG23], and $\mathrm{prt}\le2\,\mathrm{R}=O(\log n)$. No matching lower bound: $\mathrm{CA}=\Theta(\mathrm{fbs})$ holds only for total functions, and here $\mathrm{fbs}=2$. JainKlauck10 CGLMSG23
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(O(\log n)\) $\mathrm{CG}^{\mathrm{pub}}=\Theta(\mathrm{CA})$ survives the passage to partial functions [CGLMSG23], and \(\mathrm{CA}(f)\) is $O(\log n)$. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(O(\log n)\) The three non-private variants all collapse to $\Theta(\mathrm{CA})$ by LP duality, which is a partial-function statement [CGLMSG23]; see \(\mathrm{CA}(f)\). CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(O(\log n)\) As \(\mathrm{CG}^{*}(f)\): $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=O(\log n)$ [CGLMSG23]. Private-coin \(\mathrm{CG}(f)\) is the one variant that escapes the collapse, so it is left blank. CGLMSG23

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

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

Separations it witnesses

Notes

[BenOrHassidim08] give a quantum algorithm of expected cost below $0.32\log_2 n$ -- better than the best worst-case exact constant. The zoo has no expected-cost quantum measure (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) and \(\mathrm{R}_{0}(f)\) are randomized, \(\mathrm{Q}_{0}(f)\) counts worst case), so it cannot be filed as a value; note also that their abstract says "error free" while their §3 says $o(1)$ failure probability.

Open: the constant; whether the $(\log\log n)^2$ loss in $\widetilde{\deg}$ is removable; and $\widetilde{\deg}$ of the reconstruction version.