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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{C}^1(f) = 1\)
-
\(\mathrm{s}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{s}(f) = n\) against \(\mathrm{s}^1(f) = 1\)
-
\(\mathrm{s}^0(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{s}^0(f) = n\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{bs}(f_n) \to \infty \ \text{ while } \ \mathrm{UC}_{\min}(f_n) = O(1)\)from \(\mathrm{bs}(f) = n\) against \(\mathrm{UC}_{\min}(f) = 1\)
-
\(\mathrm{fbs}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^1(f_n) = O(1)\)from \(\mathrm{fbs}(f) = n\) against \(\mathrm{bs}^1(f) = 1\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{NQ}(f_n) = O(1)\)from \(\mathrm{C}(f) = n\) against \(\mathrm{NQ}(f) = 1\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}(f_n) = O(1)\)from \(\mathrm{C}^0(f) = n\) against \(\mathrm{rdeg}(f) = 1\)
-
\(\mathrm{RC}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{RC}(f) = \Theta(n)\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{bs}^0(f_n) \to \infty \ \text{ while } \ \deg(f_n) = O(1)\)from \(\mathrm{bs}^0(f) = n\) against \(\deg(f) = 1\)
-
\(\mathrm{Q}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{rdeg}_{\varepsilon}(f) = 1\)
-
\(\lambda(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\lambda(f) = \sqrt n\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\widetilde{\deg}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{ndeg}(f_n) = O(1)\)from \(\widetilde{\deg}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{ndeg}(f) = 1\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{s}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{s}(f) = n\) against \(\mathrm{C}^1(f) = 1\)
… and 119 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Unbounded: $\deg = 1$ while $\widetilde{\deg} = \Theta(\sqrt n)$. For total $f$ the exact multilinear representation is automatically $\{0,1\}$-valued on the cube, hence bounded, so $\widetilde{\deg} \le \deg$ is a triviality; on a promise the representing polynomial may be unbounded off the domain and the inequality fails outright.
-
Unbounded: $\mathrm{rdeg} = \mathrm{rdeg}_{1/3} = 1$ against $\widetilde{\deg} = \Theta(\sqrt n)$.
-
Unbounded: $\mathrm{UC}_{\min} = \mathrm{C}_{\min} = 1$ against $\mathrm{D} = n$, so the total-function bound $\mathrm{D} \le \mathrm{UC}_{\min}^2$ [BHT17] does not survive a promise.
Cited as a witness by
-
\(\deg(\mathrm{SEARCH}^{\le 1}_n) = 1 \text{ while } \widetilde{\deg}(\mathrm{SEARCH}^{\le 1}_n) = \Theta(\sqrt n)\)