Q The Query Complexity Zoo
\(\mathrm{ApproxHW}\)

Approximate Hamming weight

Total search problem with $\mathrm{R}=O(1)$ but $\mathrm{psD}=\Omega(n)$: reproducibility is exponentially expensive.

relation relational arity: $n$ bits

Description

Output any integer $w$ with $\big|\,w - |x|\,\big| \le \varepsilon n$. Random sampling gives an estimate with $O(1/\varepsilon^2)$ queries; but a pseudo-deterministic algorithm must commit to one canonical $w$ for each $x$, and near the boundaries that forces $\Omega(n)$ queries.

Measure values

MeasureValueNotes
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(1)\) At constant $\varepsilon$; the honest dependence is $\Theta(1/\varepsilon^2)$ samples for an $\varepsilon n$-accurate estimate.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) The $\Omega(n)$ side is the theorem; $\mathrm{psD} \le \mathrm{D} = O(n)$ closes it. CDM23 GIPS21
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(n)\) Reading all $n$ bits is enough, and $\mathrm{D} \ge \mathrm{psD} = \Omega(n)$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) putative After $q$ queries the unseen coordinates leave $|x|$ uncertain within a window of width $n-q$, so a never-wrong algorithm cannot stop before $q \ge (1-2\varepsilon)n$. This is the sharper statement: it is not just canonicity that costs, plain certainty already does.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(1)\) At most $\mathrm{R}$, and at least a constant.
\(\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}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(1)\) putative Uniform sampling is non-adaptive.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\Theta(n)\) Between $\mathrm{D}=\Theta(n)$ and the trivial $n$.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(1)\) Sandwiched between $\mathrm{Q} = \Theta(1)$ and $\mathrm{R} = \Theta(1)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(1)\) Sandwiched: $\mathrm{D}_\mu \le \mathrm{R} = \Theta(1)$ for every $\mu$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(0\) putative Vacuously: an input is critical for \(\mathrm{cbs}(S)\) when it has a unique valid answer, and here the valid answers at $x$ are all integers in $[\,|x|-\varepsilon n,\ |x|+\varepsilon n\,]$, an interval containing $\ge 2\varepsilon n \ge 2$ of them. So there are no critical inputs and the maximum in the definition is empty. Critical block sensitivity is blind to approximate-counting hardness, which is why the $\mathrm{psD}$ lower bound of [CDM23] needs a different technique.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n)\) putative A partial assignment fixing $q$ coordinates leaves $|x|$ free in a window of width $n-q$, so it forces a single valid answer only when $n - q \le 2\varepsilon n$, i.e. $q \ge (1-2\varepsilon)n$. Fixing that many coordinates does certify. So even nondeterministically this problem is hard, unlike \(\mathrm{Find1}_{\ge n/2}\) where $\mathrm{C}=1$.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(n)\) putative In the Prover--Delayer game the Delayer can defer on every query -- both answers keep at least two candidate outputs alive -- until $(1-2\varepsilon)n$ coordinates are fixed, scoring a point each round. So $\mathrm{rank} \ge (1-2\varepsilon)n$, and $\mathrm{rank} \le \mathrm{D} = \Theta(n)$.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n)}\) putative Each leaf subcube must force a valid answer, hence has codimension $\ge (1-2\varepsilon)n$ by the certificate bound above, hence contains at most $2^{2\varepsilon n}$ inputs; so at least $2^{(1-2\varepsilon)n}$ leaves are needed, and $2^n$ suffice. This is the worst-case analogue of the $\exp(\widetilde\Omega(n^{1/4}))$ pseudo-deterministic size bound of [CDM23].
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$ by Yao, and at least one query.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(1)\) putative Reading $O(1/\varepsilon^2)$ random positions $O(1)$ times each still estimates the density to within $\varepsilon$, since the noise only rescales the empirical mean by a known factor $1-2p$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = \Theta(1)$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(1)\) A lower bound on $\mathrm{R} = \Theta(1)$, and at least a constant.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(1)\) Squeezed by $\mathrm{cjdeg} \le \mathrm{R} = \Theta(1)$ and $\mathrm{cjdeg} \ge 1$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(1)\) From $\mathrm{prt} \le 2\mathrm{R} = O(1)$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(1)\) From $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(1)\) A lower bound on $\mathrm{Q} = \Theta(1)$, and at least $1$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both $\Theta(1)$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(n)\) putative Equal to $\mathrm{C}$: the counting argument there -- a partial assignment fixing $q$ coordinates leaves $|x|$ free in a window of width $n-q$ -- is input-independent, so every input needs $(1-2\varepsilon)n$ fixed coordinates. Certificate-uniform hardness is what drives the $\mathrm{R}_0$ and $\mathrm{DTsize}$ bounds above.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$, and at least $1$.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$. Against $\mathrm{C}^1 = \mathrm{rank} = \mathrm{psD} = \Theta(n)$ this is an unbounded gap in each case -- the cheapest relational witness the zoo has for those three against the non-adaptive noisy model.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\)· putative Zero error forces a certificate on every branch, quantumly too: a zero-error algorithm's final state is supported on outcomes valid for every input consistent with what it has learned, and by $\mathrm{C}_{\min} = (1-2\varepsilon)n$ nothing short of that many queries pins an answer down. And $\mathrm{Q}_0 \le \mathrm{R}_0 = \Theta(n)$. So quantum buys nothing at all once error is forbidden -- against $\mathrm{Q} = \Theta(1)$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(n)\) Same count as $\mathrm{C}$ and $\mathrm{C}_{\min}$: certifying any valid answer needs $(1-2\varepsilon)n$ fixed coordinates, at every input.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) Squeezed between $\mathrm{Q}_0 = \Theta(n)$ and $\mathrm{D} = \Theta(n)$.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(n)\) putative Parity queries do not count either. After $q$ parity queries the consistent inputs form an affine space $A$ of dimension $n-q$; choosing $n-q$ free coordinates, every pattern on them occurs, so $A$ contains an input of weight $\le q$ (free part all $0$) and one of weight $\ge n-q$ (free part all $1$). A leaf can name one valid $w$ only if the weights inside $A$ span at most $2\varepsilon n$, forcing $n - 2q \le 2\varepsilon n$, i.e. $\mathrm{D}^{\oplus} \ge (1-2\varepsilon)n/2$. And $\mathrm{D}^{\oplus} \le \mathrm{D} = \Theta(n)$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) putative For a search problem, one-sided error means the output is always valid. Every leaf that outputs some $w$ must have pinned $|x|/n$ to within $\varepsilon$ with certainty, which takes $(1-2\varepsilon)n$ queries; since every input reaches an outputting leaf with probability $\ge 2/3$, the cost is $\Omega(n)$. So $\mathrm{R}^1 = \Theta(\mathrm{R}_0) = \Theta(n)$, against $\mathrm{R} = \Theta(1)$ -- the same collapse that makes $\mathrm{R}_0$ jump.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\) At most $\mathrm{Q} = \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. 151 in total, strongest first.

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

Separations it witnesses

Cited as a witness by