Dense marked bit
Zero-error randomized cost $O(1)$ against $\deg = \mathrm{Q}_E = \Theta(n)$: the cheapest witness that exact degree is not bounded by any function of $\mathrm{R}_0$ off the promise.
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 $n/2$ cells are marked, and all marked cells hold the same bit $v$. Output $v$.
Exactly \(\mathrm{MARK}_n\)'s promise with "at least one mark" strengthened to "at least half the cells marked". That one change collapses every randomized and bounded-error measure to a constant -- sample a cell, it is marked with probability $\ge 1/2$, and a mark is a certificate -- while leaving the exact measures at $\Theta(n)$.
Formal definition
Writing $y_b = \mathbb{1}[x_b = 1]$ and $z_b = \mathbb{1}[x_b = 0]$, the promise makes one of $y, z$ identically zero, so $\mathrm{Dom}(f) = \{(y, 0^n) : |y| \ge n/2\} \cup \{(0^n, z) : |z| \ge n/2\}$, with $f = 1$ on the first part and $0$ on the second. Note $(0^n, 0^n)$ -- the all-blank array -- is not in the domain, and that single missing point is the whole story below.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(1)\) putative | At most $4$. Pick a uniformly random cell $b$ and query $y_b$; if it is $1$, output $1$ -- correct with certainty, since by the promise no domain input carries marks of both colours. Otherwise query $z_b$; if it is $1$, output $0$. Otherwise the cell is blank: discard it and repeat with a fresh random cell. At least half the cells are marked, so each round succeeds with probability $\ge 1/2$ and costs $\le 2$ queries; the expected total is $\le 4$. The algorithm never answers without holding a mark, so it is zero-error, and \(\mathrm{R}_{0}(f)\) is the expected-cost measure, which is what makes this legal -- the worst-case count is $\Omega(n)$, since an unlucky run can sample every blank cell first. |
| \(\deg(f)\) Exact degree | \(n/2+1\) putative | Exactly. Upper: $\deg \le \mathrm{D} = n/2+1$. Lower: let $p$ be exact on $\mathrm{Dom}$ and symmetrise over the $n$ cells. Each cell takes one of three values, so Minsky--Papert symmetrisation [MinskyPapert69] gives a polynomial $P(a,c)$ of no higher total degree in the two counts $a = |y|$ and $c = |z|$. The domain says $P(a,0) = 1$ for every integer $a \in [n/2,\, n]$ and $P(0,c) = 0$ for every integer $c \in [n/2,\, n]$ -- that is $n/2+1$ points each. Suppose $\deg p \le n/2$. Then $u(a) := P(a,0)$ is a univariate of degree $\le n/2$ agreeing with the constant $1$ at $n/2+1$ points, so $u \equiv 1$; symmetrically $w(c) := P(0,c) \equiv 0$. But $u(0) = P(0,0) = w(0)$, so $1 = 0$. Hence $\deg p \ge n/2+1$. The contradiction lives at the all-blank array, the one point the promise omits: an exact polynomial has to commit to a value there and cannot commit to two. MinskyPapert69 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n/2+1\) putative | Exactly. Upper: query $y_1, \dots, y_{n/2+1}$, stopping at the first $1$ (answer $1$). If all are $0$ then a $1$-input would need $n/2$ marks among the remaining $n/2-1$ cells, so the answer is $0$. Lower: answer $0$ to everything. After $q_y$ of the $y$-bits and $q_z$ of the $z$-bits have come back $0$, a $1$-input is still consistent whenever $n - q_y \ge n/2$, and a $0$-input whenever $n - q_z \ge n/2$; so the algorithm cannot stop until $q_y > n/2$ or $q_z > n/2$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n/2+1\) putative | The $\mathrm{D}$ upper bound is already non-adaptive -- a fixed set of $n/2+1$ $y$-bits determines the answer -- and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Theta(n)\) | Squeezed by the two entries above: $\mathrm{Q}_E \ge \deg/2 = \Omega(n)$ [BBCMdW01], and $\mathrm{Q}_E \le \mathrm{D} = n/2+1$. Against $\mathrm{Q}_0 = \Theta(1)$: demanding certainty costs a factor of $n$ here, even though aborting sometimes is free. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(1)\) | At most $\mathrm{R}_0 = \Theta(1)$, and at least $1$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(1)\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(1)\) | Between $\mathrm{R}$ and $\mathrm{R}_0$, which agree. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(1)\) putative | Query both bits of $10$ uniformly random cells and answer from any mark found. All ten miss with probability $\le 2^{-10}$, and the queries are chosen before any answer is seen. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(1)\) | By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(1)$. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(1)\) | At most $\mathrm{R} = \Theta(1)$, and at least $1$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(1)\) | $\mathrm{Q}_0 \le 2\,\mathrm{R}_0 = \Theta(1)$ (\(\mathrm{Q}_{0}(f)\)). The contrast with $\mathrm{Q}_E = \Theta(n)$ is the sharpest form of the Las Vegas / exact distinction: both are "never wrong", but only one may say "don't know". |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Theta(1)\) | $\widetilde{\deg} \le 2\mathrm{Q} = \Theta(1)$. Against $\deg = n/2+1$: bounded approximation is free here, exactness is not. |
| \(\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 $n/2$. |
| \(\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)$. MahadevdeWolf15 |
| \(\mathrm{C}(f)\) Certificate complexity | \(1\) putative | One query, on both sides: a single marked bit rules out every input of the other value, because the promise forbids marks of both colours. As on \(\mathrm{MARK}_n\), $\mathrm{D} \le \mathrm{C}^0\mathrm{C}^1$ would read $n/2+1 \le 1$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(1\) putative | See $\mathrm{C}$: a single $0$-mark, i.e. some $z_b = 1$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(1\) putative | See $\mathrm{C}$: a single $1$-mark, i.e. some $y_b = 1$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(1\) | Every input has a $1$-query certificate. |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | No promise-preserving single flip changes the answer. From a $1$-input, setting some $y_b$ to $1$ keeps the answer $1$; clearing a $y_b$ either keeps it $1$ or drops below $n/2$ marks and leaves the promise; and setting any $z_b$ to $1$ creates marks of both colours, also off the promise. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(0\) | See $\mathrm{s}$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(0\) | See $\mathrm{s}$. |
| \(\lambda(f)\) Spectral sensitivity | \(0\) | The sensitivity graph has no edges at all (see $\mathrm{s} = 0$), so its adjacency matrix is zero. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(1\) putative | At any $x$ every sensitive block must clear all of $x$'s marks and plant $n/2$ of the other colour, so all sensitive blocks at $x$ share the coordinates of $x$'s marks and no two are disjoint. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(1\) | See $\mathrm{bs}$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(1\) | See $\mathrm{bs}$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(1\) putative | The load constraint at any one of $x$'s marked coordinates 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]; also $\mathrm{QC} \le \mathrm{Q} = \Theta(1)$. Aaronson08 |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(1\) | Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 1$. GoosPitassi14 |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(1)\) | The certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 1$, and $\mathrm{Adv} \ge 1$. SpalekSzegedy06 |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(1)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(1)\) | $\gamma_2^{\alpha} = \Theta(\mathrm{Q}) = \Theta(1)$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(1)\) | A lower bound on $\mathrm{R} = \Theta(1)$, and at least $1$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(1)\) | Degenerate for Boolean functions: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(1)$. 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/2+1$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(\Theta(n)\) putative | Upper: the caterpillar above has $O(n)$ leaves. Lower: a tree with $L$ leaves has depth $\le L-1$, and the depth is at least $\mathrm{D} = n/2+1$. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(0\) putative | Every subcube inside the promise is monochromatic, by the argument on \(\mathrm{MARK}_n\): a subcube holding both a $1$-input and a $0$-input has some $y_b$ and some $z_c$ free, hence also contains the point setting both to $1$ -- marks of two colours, or the invalid encoding $11$, and off the domain either way. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(1)\) | Sandwiched: $\Omega(\mathrm{Q}) \le \mathrm{R}^{*} \le \mathrm{R} = \Theta(1)$. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(1)\) | At most $O(\mathrm{R}\log \mathrm{R}) = O(1)$, and at least $\mathrm{R} = \Theta(1)$. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(1)\) | Sandwiched: $\mathrm{prt}_\varepsilon \le \mathrm{R} = \Theta(1)$, and at least $1$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(1)\) | Sandwiched: $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon = \Theta(1)$, and at least $1$. |
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. 48 in total, strongest first.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{0}(f_n) = O(1)\)from \(\mathrm{D}(f) = n/2+1\) against \(\mathrm{R}_{0}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Theta(n)\) against \(\mathrm{C}(f) = 1\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{R}^{1}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = n/2+1\) against \(\mathrm{R}^{1}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{\mathrm{E}}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}(f) = \Theta(n)\) against \(\mathrm{s}^0(f) = 0\)
-
\(\deg(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mu}_{\varepsilon}(f_n) = O(1)\)from \(\deg(f) = n/2+1\) against \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{R}^{1}(f_n) = O(1)\)from \(\mathrm{D}(f) = n/2+1\) against \(\mathrm{R}^{1}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^0(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Theta(n)\) against \(\mathrm{C}^0(f) = 1\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{0}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = n/2+1\) against \(\mathrm{R}_{0}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{\mathrm{E}}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}(f) = \Theta(n)\) against \(\mathrm{s}^1(f) = 0\)
-
\(\deg(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{\varepsilon}(f_n) = O(1)\)from \(\deg(f) = n/2+1\) against \(\mathrm{R}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{0}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Theta(n)\) against \(\mathrm{R}_{0}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{\mathrm{E}}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}(f) = \Theta(n)\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\deg(f_n) \to \infty \ \text{ while } \ \bar{\mathrm{R}}_{\varepsilon}(f_n) = O(1)\)from \(\deg(f) = n/2+1\) against \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{R}^{1}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Theta(n)\) against \(\mathrm{R}^{1}(f) = \Theta(1)\)
… and 34 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Unbounded: $\mathrm{R}_0 = \Theta(1)$ against $\deg = n/2+1$. Zero-error randomized cost puts no bound at all on exact degree off the promise -- the algorithm gets to stop as soon as it holds a certificate, while the polynomial must still assign a single value to the all-blank array that both branches of the promise demand be different.
-
Unbounded: $\mathrm{R}_0 = \Theta(1)$ against $\mathrm{Q}_E \ge \deg/2 = \Omega(n)$.
-
Unbounded: $\mathrm{Q}_0 = \Theta(1)$ against $\mathrm{Q}_E = \Theta(n)$. Both models are never wrong; the Las Vegas one may abort, and off the promise that permission is worth a factor of $n$.
-
Unbounded: $\widetilde{\deg} = \Theta(1)$ against $\deg = n/2+1$, with the gap as wide as the arity allows.