Q The Query Complexity Zoo
\(\mathrm{SEARCH}^{0/2}_n\)

Two-or-none search

\(\mathrm{SEARCH}^{\le 1}_n\) with the promise moved from $|x|\le 1$ to $|x|\in\{0,2\}$. No two domain points are now adjacent, so $\mathrm{s} = \lambda = 0$, while $\mathrm{Q} = \mathrm{Adv} = \Theta(\sqrt n)$ is untouched.

partial quantum arity: $n$ bits

Description

Promise: $|x| \in \{0, 2\}$. Decide whether $|x| = 2$.

Formal definition

$\mathrm{Dom}(f) = \{0^n\} \cup \{e_i + e_j : i < j\}$, with $f(0^n) = 0$ and $f(e_i+e_j) = 1$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(n-1\) putative Adversary: answer $0$. After $n-2$ queries the two unread coordinates may both be $1$ or both be $0$, and both completions are on the promise. Conversely $n-1$ queries suffice: a $1$ anywhere settles the answer immediately, and if the first $n-1$ are all $0$ then the last coordinate cannot be $1$ alone, since $|x| = 1$ is off the promise.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) putative Against $0^n$ versus a uniformly random pair, $q$ queries miss both planted ones with probability $\binom{n-q}{2}/\binom n2 \ge (1 - q/n)^2$, so $q = \Omega(n)$; and $\mathrm{R} \le \mathrm{D} = n-1$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Squeezed: $\mathrm{R} \le \mathrm{R}_0 \le \mathrm{D}$, and both ends are $\Theta(n)$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\sqrt n)\) Upper: amplitude amplification with a known count of $2$ marked items, $O(\sqrt{n/2})$ queries. Lower: the adversary bound below. Grover96 Ambainis02
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(\sqrt n)\) putative Take $X = \{0^n\}$, $Y = \{e_i + e_j\}$ and relate everything to everything. Then $m = \binom n2$, $m^{\prime} = 1$, $\ell = n-1$ (from $0^n$, the pairs differing at a fixed $i$ are those containing $i$) and $\ell^{\prime} = 1$, so Ambainis' bound gives $\Omega\big(\sqrt{mm^{\prime}/\ell\ell^{\prime}}\big) = \Omega(\sqrt n)$. The ceiling is $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = O(\sqrt n)$. Ambainis02
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\sqrt n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(\sqrt n)$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) putative The neighbours of $0^n$ all have $|x| = 1$ and are off the promise.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) putative The neighbours of a weight-$2$ point have weight $1$ or $3$.
\(\mathrm{s}(f)\) Sensitivity \(0\) putative Any two domain points differ in at least two coordinates, so the sensitivity graph is edgeless. This is the entire point of the function: it is \(\mathrm{SEARCH}^{\le 1}_n\) with the distance-$1$ pairs deleted from the domain, and deleting them costs nothing quantumly.
\(\lambda(f)\) Spectral sensitivity \(0\) putative The spectral norm of the empty graph.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(0\) putative The support of a product distribution is a subcube, and a subcube of dimension $k \ge 1$ inside the domain would contain points of $k+1$ consecutive Hamming weights, of which at most one lies in $\{0,2\}$. So every product $\mu$ is a point mass and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \Theta(n)$. See \(\mathrm{forr}\) for the general shape of this collapse.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\lfloor n/2 \rfloor\) putative A block flipped at $0^n$ must land on the promise, so it is a pair, and $\lfloor n/2\rfloor$ disjoint pairs are available. Note $\mathrm{bs}^0 = \Theta(n)$ against $\mathrm{s}^0 = 0$: blocks survive the thickening, single bits do not.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(1\) putative From $e_i + e_j$ the only block whose flip both stays on the promise and changes the value is $\{i,j\}$ itself; flipping one of the two, or a pair of zeros, leaves the domain, and flipping $\{i,k\}$ gives another $1$-input.
\(\mathrm{bs}(f)\) Block sensitivity \(\lfloor n/2 \rfloor\) putative The maximum of $\mathrm{bs}^0 = \lfloor n/2\rfloor$ and $\mathrm{bs}^1 = 1$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(n/2\) putative Exactly $n/2$ at $0^n$: giving every one of the $\binom n2$ pairs weight $1/(n-1)$ loads each coordinate to exactly $1$ and totals $n/2$, and no assignment beats it, since summing the load over coordinates counts each pair twice, giving $2\sum_B w_B \le n$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n-1\) putative A partial assignment of $n-2$ zeros leaves two free coordinates that may both be $1$, a $1$-input; $n-1$ zeros force the last coordinate to $0$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(1\) putative The single literal $x_i = 1$ is consistent with $n-1$ different $1$-inputs, but it already forces the value: weight $1$ is off the promise, so any domain point with $x_i = 1$ has weight $2$.
\(\mathrm{C}(f)\) Certificate complexity \(n-1\) putative The maximum of $\mathrm{C}^0 = n-1$ and $\mathrm{C}^1 = 1$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(1\) putative A single literal $x_i = 1$ already forces $f = 1$, because weight $1$ is off the promise.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) putative Squeezed between $\mathrm{fbs} = n/2$ and $\mathrm{C} = n-1$.
\(\deg(f)\) Exact degree \(1\) putative $p(x) = \tfrac12\sum_i x_i$ is $0$ at $0^n$ and $1$ at every weight-$2$ point, so it agrees with $f$ on the whole domain. Off the promise it runs up to $n/2$, which the partial-function definition of $\deg$ permits.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\sqrt n)\) putative Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(\sqrt n)$. Lower: symmetrise to a univariate $q$ of the same degree with $q(0) \le 1/3$, $q(2) \ge 2/3$ and $|q(k)| \le 4/3$ at every integer $k \in [0,n]$ -- the off-promise boundedness is what makes $\widetilde{\deg}$ differ from $\deg$ here. Ehlich--Zeller upgrades that to boundedness on $[0,n]$, and Markov's inequality $\max|q^{\prime}| \le 2d^2\max|q|/n$ against a jump of $1/3$ across an interval of length $2$ gives $d = \Omega(\sqrt n)$. NayakWu99 Paturi92
\(\mathrm{sdeg}(f)\) Sign degree \(1\) putative $1 - \sum_i x_i$ is $+1$ on the $0$-input and $-1$ on every $1$-input.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(1\) $\sum_i x_i$ is nonzero exactly on the $1$-inputs of the domain.
\(\mathrm{rdeg}(f)\) Rational degree \(1\) Both halves are degree $1$: $\sum_i x_i$ vanishes exactly on the $0$-input, and $2 - \sum_i x_i$ exactly on the $1$-inputs.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(1\) $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = 1$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$. deWolf03
\(\mathrm{rank}(f)\) Decision tree rank \(1\) putative "Query $x_1$; if $1$ output $1$, else query $x_2$; ..." is a caterpillar, so its rank is $1$ -- and it is correct precisely because one observed $1$ already forces $|x| = 2$.

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

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

Separations it witnesses

  • Unbounded: $\lambda = 0$ while $\mathrm{Adv} = \Theta(\sqrt n)$. Since $\lambda$ is exactly zero, no bound $\mathrm{Adv} \le g(\lambda)$ of any shape survives -- it would read $\mathrm{Adv} \le g(0)$. On total functions $\lambda \le \mathrm{Adv} \le O(\lambda^4)$ by Huang's theorem; the upper half is promise-only false, and this is the witness.
  • Unbounded: $\mathrm{s} = 0$ while $\mathrm{Adv} = \Theta(\sqrt n)$. The positive adversary needs a pair of differing inputs, not a pair of adjacent ones, and thickening the promise by one destroys the second without touching the first.
  • Unbounded, and about as cleanly as possible: $\mathrm{s} = 0$ exactly while $\mathrm{bs} = \lfloor n/2\rfloor$, since every sensitive block at $0^n$ is a pair.