Marked bit
The certificate barrier at full strength: $\mathrm{C} = \mathrm{C}^0 = \mathrm{C}^1 = 1$, yet $\widetilde{\deg} = \mathrm{Q} = \Theta(\sqrt n)$ and $\mathrm{R} = \mathrm{D} = \Theta(n)$. Recognising the answer is one query; finding it is Grover.
partial quantum arity: $2n$ bits (an $n$-cell array over $\{0,1,2\}$, binary-encoded)
Description
The input is an array $x \in \{0,1,2\}^n$; call a cell blank when it holds $2$ and marked otherwise. Promise: at least one cell is marked, and all marked cells hold the same bit $v$. Output $v$.
The promise is \(\mathrm{SEARCH}^{\le 1}_n\)'s, made symmetric. There the $0$-input is the single all-blank string, which nothing short certifies; here both answers are carried by marks, so every input has a one-query certificate -- and the number of marks is left free, which is the whole difficulty.
Formal definition
$\mathrm{Dom}(f) = \{x : x^{-1}(\{0,1\}) \ne \emptyset$ and $|x(\mathrm{Dom})\cap\{0,1\}| = 1\}$, with $f(x) = 1$ iff some cell holds $1$. Writing $y_b = \mathbb{1}[x_b = 1]$ and $z_b = \mathbb{1}[x_b = 0]$ for the two encoding bits of cell $b$, the domain is $\{(y,z) : y \wedge z = 0,\ (y,z) \ne (0,0),\ y = 0 \text{ or } z = 0\}$ and $f = \mathrm{OR}(y)$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n\) putative | Exactly. Upper: query $y_1,\dots,y_n$, the "is this cell marked $1$" bits. If any is $1$ the answer is $1$; if all are $0$ there are no $1$-marks, and the promise guarantees a mark, so the answer is $0$. Lower: answer $0$ to everything. If some cell has both encoding bits unqueried, the two single-mark inputs there are both still consistent and disagree; so every cell must be touched. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n)\) putative | Plant one mark at a uniformly random cell with a uniformly random colour. All-zero answers are what the algorithm sees unless it queries a bit of the marked cell, and each cell contributes only the bit it did not query: after $t$ queries the posterior still gives weight $\Omega((n-t)/n)$ to the other colour, so $t = \Omega(n)$. Upper: $\mathrm{R} \le \mathrm{D} = n$. |
| \(\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)$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(n)\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(n)\) | By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$; the planted-mark distribution above is the maximiser. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n\) putative | Adaptivity buys nothing: the $y_b$ algorithm is already non-adaptive, and the lower bound above needs one query per cell whatever the order. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(n)\) | Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(n)\) | Between $\mathrm{R}$ and $\mathrm{R}_0$, which agree. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(\sqrt n)\) putative | Upper: search the $2n$ encoding bits for a $1$ with the unknown-number-of-solutions version of Grover [BBHT98]; there are $m \ge 1$ of them, it finds one in $O(\sqrt{2n/m}) = O(\sqrt n)$ queries, and which bit it finds is the answer -- a $y$-bit means $1$, a $z$-bit means $0$. Lower: $\mathrm{Q} \ge \widetilde{\deg}/2 = \Omega(\sqrt n)$. Grover96 BBHT98 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Theta(\sqrt n)\) putative | The value the function exists for. Upper: $\widetilde{\deg} \le 2\mathrm{Q}$. Lower, by reduction to $\mathrm{OR}$ rather than by symmetrising: let $p$ be $\varepsilon$-approximating and $[0,1]$-valued on the whole cube, and set $P(u) = p(y=u, z=0)$ and $W(u) = p(y=0, z=u)$, both of degree $\le \deg p$. For $u \ne 0^n$ the input $(u,0)$ is a domain $1$-input and $(0,u)$ a domain $0$-input, so $P(u) \ge 1-\varepsilon$ and $W(u) \le \varepsilon$; and $P(0^n) = W(0^n) = p(0,0)$, the all-blank string, whatever that unconstrained value is. So $\Psi = P - W$ has $\Psi(0^n) = 0$, $\Psi(u) \ge 1-2\varepsilon$ off the origin, and $|\Psi| \le 1$ everywhere. So $\Psi$ is a $[-1,1]$-bounded polynomial on the cube separating $0^n$ from the rest by a constant gap ($0$ versus $\ge 1/3$ at $\varepsilon = 1/3$), which is exactly what the Nisan--Szegedy argument rules out below degree $\Omega(\sqrt n)$: symmetrise $\Psi$, and Ehlich--Zeller plus Markov give $\deg p \ge \deg \Psi = \Omega(\sqrt n)$ [NS94]. The cancellation at the origin is the point -- neither $P$ nor $W$ alone is pinned there, but their difference is. NS94 BBCMdW01 |
| \(\deg(f)\) Exact degree | \(n\) putative | Exactly, and the contrast with \(\mathrm{SEARCH}^{\le 1}_n\) ($\deg = 1$) and \(\mathrm{ApproxIndex}_k\) ($\deg = 2$) is the whole design. Upper: $1 - \prod_b (1-y_b)$. Lower: symmetrise an exact $p$ over the $n$ cells to $q(j_1,j_0)$, of no higher degree, and put $r(t) = q(t,0) - q(0,t)$; then $r(t) = 1$ for every integer $t \in [1,n]$ while $r(0) = 0$, so $r - 1$ has $n$ roots and is not identically zero. Counting the marks cannot work here because their number is not fixed. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(1\) putative | $\sum_b y_b - \sum_b z_b$ is positive exactly on the $1$-inputs of the domain, since one of the two sums is always $0$ and the other is at least $1$. Against $\widetilde{\deg} = \Theta(\sqrt n)$: sign-representation is free, bounded approximation is not. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(1\) | $\sum_b y_b$ is nonzero exactly on the $1$-inputs of the domain. And $\mathrm{ndeg} \ge 1$. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(1\) | $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$, and $\sum_b z_b$ does for $\bar f$ what $\sum_b y_b$ does for $f$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(1\) | $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = 1$. IJKKKSWW23 |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(1\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$. deWolf03 |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(1)\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$: guess a cell, read it, postselect on it being marked. MahadevdeWolf15 |
| \(\mathrm{C}(f)\) Certificate complexity | \(1\) putative | One query, at every input and on both sides. Any marked cell certifies: by the promise no domain input has marks of both colours, so seeing a single $1$-mark rules out every $0$-input and vice versa. This is the sharpest form of the promise-problem lesson -- $\mathrm{D} \le \mathrm{C}^0\mathrm{C}^1$ would read $n \le 1$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(1\) putative | See $\mathrm{C}$: a single $0$-mark. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(1\) putative | See $\mathrm{C}$: a single $1$-mark. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(1\) putative | Equal to $\mathrm{C}$: the same one-query certificate works everywhere. |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | No single flip stays on the promise while changing the answer. Adding a mark of the same colour or removing one of several leaves the value alone; removing the last mark, or adding a mark of the other colour, or setting a cell's two encoding bits to $11$, all leave the domain. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ and the sensitivity graph has no edges at all. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(0\) putative | See $\mathrm{s}$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(0\) putative | See $\mathrm{s}$. |
| \(\lambda(f)\) Spectral sensitivity | \(0\) putative | The sensitivity graph is empty (see $\mathrm{s}$), so every bound of the form $M \le g(\lambda)$ fails here at once -- it would read $M \le g(0)$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(1\) putative | An answer-flipping block must clear every current mark and plant one of the other colour, so all sensitive blocks contain the encoding bit of some fixed existing mark and no two are disjoint. There is at least one, so $\mathrm{bs} = 1$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(1\) putative | See $\mathrm{bs}$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(1\) putative | See $\mathrm{bs}$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(1\) putative | The load constraint at a single existing mark already caps $\sum_B w_B$ at $1$, since every sensitive block contains it. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(1\) | Equal to $\mathrm{fbs}$ by LP duality. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(1)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$, and also $\mathrm{RC} \le \mathrm{C} = 1$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{FC}}) = \Theta(1)$ [Aaronson08]. Constant quantum certificate complexity against $\mathrm{Q} = \Theta(\sqrt n)$ -- the same phenomenon Aaronson exhibits on \(\mathrm{COL}_n\), here at quadratic strength and with a two-line proof. Aaronson08 |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(1)\) | The certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 1$, which holds for partial $f$ too. So the positive-weight adversary proves nothing about a function whose $\mathrm{Q}$ is $\Theta(\sqrt n)$ -- and the barrier is not the usual property-testing shape here, since a $1$-input and a $0$-input can be a Hamming distance $2$ apart. SpalekSzegedy06 Zhang05 |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(\sqrt n)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. The gap to $\mathrm{Adv} = \Theta(1)$ is as wide as the function is hard. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(\sqrt n)\) | $\gamma_2^{\alpha} = \Theta(\mathrm{Q})$. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(\sqrt n)\) | Sandwiched between $\mathrm{Adv}^{\pm} = \Theta(\sqrt n)$ and $\mathrm{Q} = \Theta(\sqrt n)$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Omega(\sqrt n),\ O(n)\) | Between $\mathrm{Q}$ and $\mathrm{R}_0$. Zero error cannot be cheap -- a zero-error algorithm must actually exhibit a mark -- but no bound better than the sandwich is recorded. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Omega(\sqrt n),\ O(n)\) | Between $\mathrm{Q}_0$ and $\mathrm{D}$. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(0\) putative | Every subcube inside the promise is monochromatic, so no product distribution is hard at all. If a subcube held a $1$-input and a $0$-input then some $y_b$ and some $z_c$ would both be free in it, and the subcube would also contain the point with $y_b = z_c = 1$ -- marks of both colours if $b \ne c$, the invalid encoding $11$ if $b = c$, and off the domain either way. Against $\mathrm{R} = \Theta(n)$; see \(\mathrm{forr}\). |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(1\) | Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 1$. GoosPitassi14 |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(n)\) | Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(n)$. CDM23 |
| \(\mathrm{rank}(f)\) Decision tree rank | \(1\) putative | "Query $y_1$; if $1$ output $1$, else query $y_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. 112 in total, strongest first.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{C}(f) = 1\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^0(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{C}^0(f) = 1\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{R}^{1}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}(f_n) = O(1)\)from \(\mathrm{R}^{1}(f) = \Theta(n)\) against \(\mathrm{rdeg}(f) = 1\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{RC}(f_n) = O(1)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(n)\) against \(\mathrm{RC}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{\mathrm{E}}(f_n) \to \infty \ \text{ while } \ \mathrm{fbs}(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}(f) = \Omega(\sqrt n),\ O(n)\) against \(\mathrm{fbs}(f) = 1\)
-
\(\mathrm{Q}_{0}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{Q}_{0}(f) = \Omega(\sqrt n),\ O(n)\) against \(\mathrm{C}^1(f) = 1\)
-
\(\mathrm{Adv}^{\pm}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{Adv}^{\pm}(f) = \Theta(\sqrt n)\) against \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{MAdv}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{MAdv}(f) = \Theta(\sqrt n)\) against \(\mathrm{rdeg}_{\varepsilon}(f) = 1\)
-
\(\deg(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\deg(f) = n\) against \(\mathrm{s}(f) = 0\)
-
\(\widetilde{\deg}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}(f_n) = O(1)\)from \(\widetilde{\deg}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{bs}(f) = 1\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^0(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{C}^0(f) = 1\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{C}(f) = 1\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{rdeg}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{rdeg}(f) = 1\)
… and 98 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Unbounded, and polynomially so: $\mathrm{C} = \mathrm{C}^0 = \mathrm{C}^1 = \mathrm{C}_{\min} = 1$ against $\widetilde{\deg} = \Theta(\sqrt n)$. \(\mathrm{OS}_n\) separates the same pair with published bounds but only at $\log$ scale; this pushes it to a square root, which is the most a partial function can manage against $\mathrm{C} = 1$ in the sense that $\widetilde{\deg} \le 2\mathrm{Q} \le 2\mathrm{D} \le 2n$.
-
Unbounded: $\mathrm{sdeg} = 1$ against $\widetilde{\deg} = \Theta(\sqrt n)$. The two differ only in demanding a bounded approximation rather than a correct sign, and on a promise that is worth everything.
-
Unbounded: $\mathrm{QC} = \mathrm{RC} = \Theta(1)$ against $\mathrm{Q} = \Theta(\sqrt n)$, so constant quantum certificate complexity does not make a promise problem easy.