Q The Query Complexity Zoo
\(\mathrm{SEARCH}^{\le 1}_n\)

Unique search

Grover search as a partial function. The reason it is in the zoo: $\deg = 1$ while $\widetilde{\deg} = \Theta(\sqrt n)$, so $\widetilde{\deg} \le \deg$ -- a triviality for total functions -- fails outright on a promise.

partial quantum arity: $n$ bits

Description

Promise: $|x| \le 1$. Decide whether $|x| = 1$.

Formal definition

$\mathrm{Dom}(f) = \{0^n\} \cup \{e_1,\dots,e_n\}$, with $f(0^n) = 0$ and $f(e_i) = 1$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(n\) Adversary: answer $0$ to the first $n-1$ queries; the input can still be $0^n$ or $e_i$ at the one unqueried coordinate $i$. Reading all $n$ bits obviously suffices.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Against $0^n$ versus a uniformly random $e_i$, $q$ queries see all-zero answers with probability $1 - q/n$, so $q = \Omega(n)$. The canonical quadratic quantum speed-up sits on top of this.
\(\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)\) Grover, and the $\Omega(\sqrt n)$ hybrid-argument lower bound already applies under the unique-marked promise. Grover96 BBBV97
\(\deg(f)\) Exact degree \(1\) putative $p(x) = \sum_i x_i$ agrees with $f$ at every point of the domain: it is $0$ at $0^n$ and $1$ at each $e_i$. Off the promise it grows to $n$, which the partial-function definition of $\deg$ (agree on $\mathrm{Dom}(f)$, unbounded elsewhere) permits. $f$ is not constant, so $\deg = 1$ exactly.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\sqrt n)\) putative Upper: $\widetilde{\deg} \le 2\mathrm{Q}$. Lower: symmetrise an approximating $p$ to a univariate $q$ of the same degree with $q(0) \le 1/3$, $q(1) \ge 2/3$ and $|q(k)| \le 4/3$ at every integer $k \in [0,n]$ -- and this last is exactly where the off-promise boundedness demanded of $\widetilde{\deg}$ is used. Boundedness at the integer points upgrades to boundedness on $[0,n]$ up to a constant factor while $\deg q = O(\sqrt n)$ (Ehlich--Zeller / Coppersmith--Rivlin), and then Markov's inequality $\max|q^{\prime}| \le 2 d^2 \max|q| / n$ against $q(1) - q(0) \ge 1/3$ forces $d = \Omega(\sqrt n)$. NS94 BBCMdW01 Paturi92
\(\mathrm{sdeg}(f)\) Sign degree \(1\) putative $\tfrac12 - \sum_i x_i$ is positive at $0^n$ and negative at every $e_i$.
\(\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\) $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$, and $1 - \sum_i x_i$ vanishes exactly on the $1$-inputs, so both halves are $1$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(1\) $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = 1$. Against $\widetilde{\deg} = \Theta(\sqrt n)$ this is an unbounded partial-function separation of approximate rational degree from approximate degree -- rational approximation is not required to stay bounded off the promise, and here that is worth a quadratic factor. IJKKKSWW23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$. deWolf03
\(\mathrm{s}^0(f)\) 0-sensitivity \(n\) All $n$ neighbours of $0^n$ lie in the domain and are $1$-inputs.
\(\mathrm{s}^1(f)\) 1-sensitivity \(1\) The only domain neighbour of $e_i$ is $0^n$; flipping any other coordinate leaves the promise.
\(\mathrm{s}(f)\) Sensitivity \(n\)
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(n\) Only singleton blocks keep $0^n$ inside the promise, and all $n$ of them are sensitive.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(1\) From $e_i$ the only block whose flip stays in the domain and changes the value is $\{i\}$; flipping $\{i,j\}$ gives $e_j$, another $1$-input.
\(\mathrm{bs}(f)\) Block sensitivity \(n\)
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(n\) Squeezed between $\mathrm{bs} = n$ and $\mathrm{C} = n$.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n\) Fixing only $n-1$ coordinates of $0^n$ to $0$ leaves the domain point $e_j$ at the free coordinate $j$, and that is a $1$-input.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(1\) The single literal $x_i = 1$ is satisfied by no other domain point.
\(\mathrm{C}(f)\) Certificate complexity \(n\)
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(1\) Attained at the $1$-inputs.
\(\mathrm{SP}(f)\) Subcube partition complexity \(n\) putative The $n$ subcubes $\{x_i = 1\}$ together with the single point $\{0^n\}$ partition the domain, so a partition of width $n$ exists; and no partition can do better, since the part containing $0^n$ must exclude all $n$ points $e_i$ and therefore fixes every coordinate.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n\) putative $\mathrm{UC} = \mathrm{SP}$, and the partition above is exactly an unambiguous certificate cover.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(1\) putative The $1$-certificates of that cover have width $1$, so $\mathrm{UC}^1 = 1$. With $\mathrm{D} = n$ this shows the total-function bound $\mathrm{D} \le \mathrm{UC}_{\min}^2$ [BHT17] is total-only.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) putative At $0^n$ a certificate scheme must find the planted $1$ with constant probability against an adversary free to plant it anywhere, which costs $\Omega(n)$ weight; and $\mathrm{RC} \le \mathrm{C} = n$.
\(\lambda(f)\) Spectral sensitivity \(\sqrt n\) putative The sensitivity graph is the star $K_{1,n}$ centred at $0^n$, whose adjacency matrix has spectral norm exactly $\sqrt n$. Both $\lambda \ge \sqrt{\mathrm{s}}$ and $\lambda = O(\mathrm{Q})$ are tight here.
\(\mathrm{rank}(f)\) Decision tree rank \(1\) putative "Query $x_1$; if $1$ output $1$, else query $x_2$; ..." is a caterpillar -- every internal node has a leaf child -- so its rank is $1$, against $\mathrm{D} = 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. 133 in total, strongest first.

… and 119 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