Q The Query Complexity Zoo
\(\mathrm{DMARK}_n\)

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

MeasureValueNotes
\(\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.

… and 34 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses