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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{bs}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{bs}(f) = \lfloor n/2 \rfloor\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{fbs}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{fbs}(f) = n/2\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{RC}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{RC}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = 0\)
-
\(\mathrm{bs}^0(f_n) \to \infty \ \text{ while } \ \lambda(f_n) = O(1)\)from \(\mathrm{bs}^0(f) = \lfloor n/2 \rfloor\) against \(\lambda(f) = 0\)
-
\(\mathrm{Adv}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{Adv}(f) = \Theta(\sqrt n)\) against \(\mathrm{s}^1(f) = 0\)
-
\(\mathrm{Adv}^{\pm}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt n)\) against \(\mathrm{rank}(f) = 1\)
-
\(\gamma_2^{\alpha}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}(f_n) = O(1)\)from \(\gamma_2^{\alpha}(f) = \Theta(\sqrt n)\) against \(\mathrm{rdeg}(f) = 1\)
-
\(\mathrm{bs}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{bs}(f) = \lfloor n/2 \rfloor\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{fbs}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{fbs}(f) = n/2\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{RC}(f_n) \to \infty \ \text{ while } \ \lambda(f_n) = O(1)\)from \(\mathrm{RC}(f) = \Theta(n)\) against \(\lambda(f) = 0\)
-
\(\mathrm{bs}^0(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{bs}^0(f) = \lfloor n/2 \rfloor\) against \(\mathrm{D}^{\mathrm{prod}}(f) = 0\)
-
\(\mathrm{Adv}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{Adv}(f) = \Theta(\sqrt n)\) against \(\mathrm{C}^1(f) = 1\)
-
\(\mathrm{Adv}^{\pm}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}(f_n) = O(1)\)from \(\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt n)\) against \(\mathrm{rdeg}(f) = 1\)
-
\(\gamma_2^{\alpha}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\gamma_2^{\alpha}(f) = \Theta(\sqrt n)\) against \(\mathrm{rank}(f) = 1\)
… 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.