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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{C}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = \Theta(1)\)
-
\(\mathrm{C}^1(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mu}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{C}^1(f) = \Theta(n)\) against \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = \Theta(n)\) against \(\mathrm{cbs}(S) = 0\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{R}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \bar{\mathrm{R}}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = \Theta(n)\) against \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{R}_{0}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}(f_n) = O(1)\)from \(\mathrm{R}_{0}(f) = \Theta(n)\) against \(\mathrm{noisyR}(f) = \Theta(1)\)
-
\(\mathrm{psD}(S)(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}^{\mathrm{na}}(f_n) = O(1)\)from \(\mathrm{psD}(S) = \Theta(n)\) against \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{\mathrm{E}}(f_n) \to \infty \ \text{ while } \ \mathrm{CA}(f_n) = O(1)\)from \(\mathrm{Q}_{\mathrm{E}}(f) = \Theta(n)\) against \(\mathrm{CA}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{0}(f_n) \to \infty \ \text{ while } \ \mathrm{N}_{p}(f_n) = O(1)\)from \(\mathrm{Q}_{0}(f) = \Theta(n)\) against \(\mathrm{N}_{p}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\mathrm{D}^{\oplus}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\Theta(n)}\) against \(\mathrm{D}^{\oplus}(f) = \Theta(n)\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mu}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{C}(f) = \Theta(n)\) against \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{C}^1(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{C}^1(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = \Theta(1)\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = \Theta(n)\) against \(\mathrm{R}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{cbs}(S) = 0\)
… and 137 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Exponential separation between pseudo-deterministic and randomized query complexity of a total search problem; also an $\exp(\Omega(n))$ separation in decision-tree size.
-
Unbounded: $\mathrm{R}=\Theta(1)$ but $\mathrm{R}_0=\Theta(n)$, for a total search problem. Relations with verifiable witnesses have $\mathrm{R}_0=\Theta(\mathrm{R})$; approximate counting has no witness to verify, so the collapse fails.
-
Unbounded: $\mathrm{R}^{\mathrm{na}} = \Theta(1)$ against $\mathrm{D}^{\mathrm{na}} = \Theta(n)$ -- the whole gap for this problem is randomness, not adaptivity.
-
Unbounded in the strongest possible way: $\mathrm{cbs} = 0$, because a problem whose answers come in intervals has no input with a unique valid answer, while $\mathrm{D} = \Theta(n)$. Critical block sensitivity is the standard route to relational lower bounds and it is simply unavailable for approximate counting; the same holds at \(\mathrm{Find1}_{\ge n/2}\). Every measure is therefore unbounded in terms of $\mathrm{cbs}$ over relations, but no asymptotic separation can be read off a value of exactly zero.
Cited as a witness by
-
\(\mathrm{R}(\mathrm{ApproxHW}) = O(1),\ \ \mathrm{psD}(\mathrm{ApproxHW}) = \Omega(n)\)