Non-adaptive randomized query complexity
Bounded-error cost when the query set is drawn from a distribution fixed in advance, independent of the answers.
also written:
oblivious randomized decision tree complexity
Definition
The algorithm samples a set $S \subseteq [n]$ from a distribution of its choosing, learns $x|_S$, and outputs a guess that must be correct with probability $\ge 2/3$. $\mathrm{R}^{\mathrm{na}}_\varepsilon(f)$ is the least $\max |S|$ over the support (the worst-case version; the expected-cost version is the natural companion, as for $\bar{\mathrm{R}}$).
Non-adaptivity is the standard restriction in property testing, where "adaptive vs non-adaptive" is one of the two axes (the other being one-sided vs two-sided error).
Parameters
\(\varepsilon\) (eps) default \(1/3\)
error probability
Basic facts
- $\mathrm{R}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, and in the other direction $\mathrm{R}^{\mathrm{na}}_\varepsilon(f) \le 2^{\mathrm{R}_\varepsilon(f)}-1$: sample a tree from the optimal distribution and read every variable it could ever query.
- Yao's minimax applies verbatim: $\mathrm{R}^{\mathrm{na}}_\varepsilon(f) = \max_\mu \mathrm{D}^{\mathrm{na},\mu}_\varepsilon(f)$, the max over input distributions of the best fixed query set of that size.
- Adaptivity can save exponentially even with randomness: $\mathrm{R}(\mathrm{ADDR}) = \Theta(\log n)$ while $\mathrm{R}^{\mathrm{na}}(\mathrm{ADDR}) = \Theta(n)$, since a fixed distribution over $k$ data bits finds the addressed bit with probability $\le k/n$ and must otherwise guess.
- For $\mathrm{OR}_n$ adaptivity buys nothing: $\mathrm{R}(\mathrm{OR}_n) = \Theta(n) = \mathrm{R}^{\mathrm{na}}(\mathrm{OR}_n)$.
- Non-adaptively, noise is free to resist: $\mathrm{R}^{\mathrm{na}}(f) = \Theta(\mathrm{noisyR}^{\mathrm{na}}(f))$ for every partial Boolean $f$ [BenDavidBlais20composition, Thm. 8], although the same statement is false for relations. Contrast the adaptive case, where $\mathrm{noisyR}$ can be exponentially smaller than $\mathrm{R}$.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{R}^{\mathrm{na}}(f)\). “\(\mathrm{R}^{\mathrm{na}}(f)\) in terms of it” is the pair with \(\mathrm{R}^{\mathrm{na}}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(n)\) | A fixed distribution over query sets of size $m$ leaves some coordinate unqueried with probability $\ge 1-m/n$, and $0^n$ versus $e_i$ is then undecidable; so $m=\Omega(n)$. |
| AND total | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here. |
| PARITY total | \(n\) | Leaving any coordinate unqueried leaves the answer a fair coin flip. |
| MAJORITY total | \(\Theta(n)\) | In fact $n - O(1)$, which is sharper than the recorded $\Theta(n)$ but mixes an exact and an asymptotic term, so it lives here rather than in the value. If two coordinates go unqueried the remaining $n-2$ bits can be set to split evenly, and then the two unread bits decide the answer, leaving it a fair coin flip; so every non-adaptive query set must miss at most one coordinate and $\mathrm{R}^{\mathrm{na}} \ge n-1$. The matching $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = n$ is trivial. |
| Threshold total | \(\Theta(n)\) | |
| Symmetric functions (general) total | \(\Theta(n)\) | Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$. |
| EXACT-HALF total | \(\Theta(n)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here. |
| ODD-MAX-BIT total | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here. |
| ADDRESS / multiplexer total | \(\Theta(2^k)\) | A fixed distribution over $m$ data bits contains the addressed one with probability at most $m/2^k$; otherwise the algorithm is guessing an unbiased bit. |
| Binary tree navigation total | \(\Theta(2^k)\) | On a uniformly random input the bottom node reached is uniform over the $2^{k-1}$ bottom nodes, and an algorithm that has not read it is guessing an unbiased bit; a fixed set of $m$ variables contains it with probability at most $m/2^{k-1}$. |
| TRIBES total | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here. |
| AND-OR tree (depth 2) total | \(\Theta(n^2) = \Theta(N)\) | Between $\mathrm{R} = \Theta(n^2)$ and $\mathrm{D}^{\mathrm{na}} = n^2$. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(N)\) putative | Non-adaptive randomness buys nothing on any function that depends on all its variables. Pick a uniformly random leaf $\ell$ and a fixed input making $\ell$ pivotal, then set $x_\ell$ uniformly at random. A non-adaptive algorithm reading $q$ positions hits $\ell$ with probability $\le q/N$, and otherwise sees a fixed string and must guess a uniform bit, so its success probability is at most $\tfrac12 + \tfrac{q}{2N}$. Hence $\mathrm{R}^{\mathrm{na}}_{1/3}(f) \ge N/3$ for every $f$ with all $N$ variables relevant, matching $\mathrm{D}^{\mathrm{na}} = N$. This is the general form of the \(\mathrm{ADDR}_k\) argument already recorded on the \(\mathrm{R}^{\mathrm{na}}(f)\) page, and it separates $\mathrm{R}^{\mathrm{na}} = \Theta(N)$ from $\mathrm{R} = \Theta(N^{0.753\ldots})$ here. |
| Recursive MAJORITY-of-3 total | \(\Theta(N) = \Theta(3^{\,d})\) putative | Non-adaptive randomness buys nothing on any function that depends on all its variables. Pick a uniformly random leaf $\ell$ and a fixed input making $\ell$ pivotal, then set $x_\ell$ uniformly at random. A non-adaptive algorithm reading $q$ positions hits $\ell$ with probability $\le q/N$, and otherwise sees a fixed string and must guess a uniform bit, so its success probability is at most $\tfrac12+\tfrac{q}{2N}$; hence $\mathrm{R}^{\mathrm{na}}_{1/3} \ge N/3$. Together with $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$ this pins the value, and no part of the open $\mathrm{R}$ exponent is needed. |
| Kushilevitz's function (iterated) total | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with both ends $N$ here. |
| Rubinstein's function total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}}(f) = N$ here. |
| Ambainis-Sun function total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs} \le \mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$, with $\mathrm{fbs} = \Theta(N)$ here. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{fbs} = \Theta(n^2)$ and $\mathrm{D}^{\mathrm{na}} = n^2$ here. |
| Meiburg's tournament-subcube function total | \(\ge 14011^{\,d}\) putative | $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Omega(\mathrm{bs})$. |
| Pointer functions total | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Variant $f_{2m,m}$: $\mathrm{R}\le\mathrm{R}^{\mathrm{na}}\le\mathrm{D}^{\mathrm{na}}=\widetilde\Theta(n)$, with $\mathrm{R}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$. Nonadaptivity is expected to cost the full input length here, since the whole point of the pointer payload is that queries must chase a chain. |
| Cheat-sheet functions total | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n)$. The ceiling is the cheat-sheet input length $n^{10+o(1)}$, which is not comparable to the other entries in this scale. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3})\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n^{4/3})$. |
| Gilmer-Saks-Srinivasan functions total | \(\Theta(n^2)\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\Omega(n^2)$; the ceiling is $\mathrm{D}^{\mathrm{na}}=n^2$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{D}^{\mathrm{na}}=\widetilde\Theta(n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{2/3})\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n^{2/3})$. |
| Ambainis' exact-quantum function total | \(3^d\) | Squeeze: $\mathrm{R}\le\mathrm{Rna}\le\mathrm{Dna}$. |
| FORRELATION partial | \(\widetilde\Theta(\sqrt n)\)· putative | The $O(\sqrt n)$ algorithm samples coordinates of $x$ and $y$ from its coins and forms an estimator of $\langle\hat x, y\rangle$, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \widetilde\Theta(\sqrt n)$. |
| k-FORRELATION partial | \(\widetilde\Theta\!\big(n^{1-1/k}\big)\)· putative | The randomized upper bound is an estimator built from coordinates sampled from the coins alone, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$. Adaptivity buys nothing here, exactly as for \(\mathrm{forr}\). |
| Simon's problem partial | \(\Theta(2^{n/2})\) putative | Sampling $O(2^{n/2})$ uniformly random points is non-adaptive, and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(2^{n/2})$. |
| Deutsch-Jozsa partial | \(\Theta(1)\) putative | Read $10$ fixed positions and answer "balanced" iff they are not all equal; a balanced input fools this with probability $2^{-9}$. |
| Bernstein-Vazirani partial | \(\Theta(n)\) putative | Same non-adaptive algorithm; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$. |
| Marked bit partial | \(\Theta(n)\) | Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| Dense marked bit partial | \(\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. |
| Unstructured search (relation) relation | \(\Theta(n)\) | Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| FIND-1 under a density promise relation | \(\Theta(1)\) putative | Sampling is already non-adaptive: read $10$ uniformly random positions and output any that is $1$. |
| Approximate Hamming weight relation | \(\Theta(1)\) putative | Uniform sampling is non-adaptive. |
| Correlated-string search relation | \(\Theta(\sqrt n)\) putative | The algorithm above never looks at an answer before choosing the next query, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Omega(\sqrt n)$. |
| SearchCNF relation | \(\Theta(1)\)· putative | Sampling a clause of $\varphi$ at random and reading its $k$ variables is non-adaptive; for a random $\Delta$-dense $\varphi$ a constant fraction of clauses is falsified by any fixed assignment, so $O(1)$ tries suffice. |
| Gap-Majority partial | \(\Theta(\min(n, 1/\delta^2))\) | Sampling is non-adaptive, and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$. |
| Gap-Majority at constant gap partial | \(\Theta(1)\) | Sampling is non-adaptive. |
| Parity-labelled FIND-1 partial | \(\Theta(1)\) putative | Sampling needs no adaptivity: read $10$ uniformly random positions and answer from any that is $1$. A position is $1$ with probability $1/4$, so this fails with probability $(3/4)^{10} < 0.06$. |
| Approximate index partial | \(\Theta(\sqrt{k\log k})\) putative | Same remark: the randomized algorithm reads a fixed prefix of $a$ and one array cell chosen from the coins alone, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$. |
| Collision problem partial | \(\Theta(\sqrt n)\) putative | Sampling $c\sqrt n$ positions is non-adaptive and finds a collision with constant probability; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(\sqrt n)$. Adaptivity is worth nothing here. |
| Element distinctness total | \(\Theta(n)\) | Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| Ambainis-Belovs function partial | \(\Omega(n^{1/3})\) | Between $\mathrm{R} = \Omega(n^{1/3})$ and $\mathrm{D}^{\mathrm{na}} = O(n)$. |
| Ben-David-Kundu total search problems relation | \(\widetilde\Omega(\sqrt n)\) | At least $\mathrm{R}$. |
| Yamakawa-Zhandry problem relation | \(2^{\Omega(n)}\) | At least $\mathrm{R}$. |
| Surjectivity total | \(\Theta(n)\) | Sandwiched: $\mathrm{R}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$ here. |
| $k$-distinctness total | \(\Theta(n)\) | Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | Sandwiched between $\mathrm{R} = \Theta(m^2)$ and $\mathrm{D}^{\mathrm{na}} = \binom m2$. |
| Recursive Fourier sampling partial | \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}_{\varepsilon}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R} = n^{\Omega(\log n)}$ and $\mathrm{D}^{\mathrm{na}} = O(n^{\ell})$ here, so at $\ell = \log n$ the two ends meet at $n^{\Theta(\log n)}$. |
| Welded trees relation | \(\Theta(4^n)\) putative | Randomness does not help the non-adaptive algorithm either, so $\mathrm{R}^{\mathrm{na}}/\mathrm{R} = \tilde\Theta(2^{3n/2})$ as well. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = \Theta(4^n)$. Lower: let the algorithm draw a random name set $S$, $|S| = t$. Since $\pi$ is a uniformly random injection with only $\pi(\mathrm{ENTRANCE})$ pinned, the exit and its two neighbours land in $S$ with probability at most $3t/(2^{2n}-1)$; conditioned on missing all three, the transcript is independent of which unqueried unused name carries the exit, and there are $2^{2n} - t - 2^{n+2}$ candidates. So the success probability is at most $3t/(2^{2n}-1) + o(1)$, and $t = \Omega(4^n)$ is needed for $2/3$. |
| Local search on the hypercube relation | \(\Theta(2^n)\) putative | Randomness buys nothing without adaptivity, and the gap against $\mathrm{R} = \Theta(2^{n/2}\sqrt n)$ is quadratic. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = 2^n$. Lower: pick $u$ uniformly and let $f$ be the Hamming distance to $u$ except at $u$ itself, where $f(u) \in \{0, 2n\}$ with a fair coin. Both completions are legal, the reading on any cell other than $u$ is identical, and the valid outputs are disjoint -- $\{u\}$ in one case, the $n$ neighbours of $u$ in the other. A fixed query set $S$ of size $t$ contains $u$ with probability $t/2^n$, so the success probability is at most $t/2^n + 1/2$ and $t \ge 2^n/6$. |
| Local search on the grid relation | \(\Theta(k^d)\) putative | Every cell, even with randomness, so $\mathrm{R}^{\mathrm{na}} = \Theta(\mathrm{D}^{\mathrm{na}}) = \Theta(N)$. Randomise the \(\mathrm{D}^{\mathrm{na}}(f)\) construction: draw $u$ uniformly from $[k]^d$, let $f$ be the $\ell_1$ distance to $u$ off $u$, and set $f(u) \in \{0, 2dk\}$ by a fair coin. The two completions have disjoint solution sets and agree everywhere but $u$, so a fixed query set of size $t$ succeeds with probability at most $t/k^d + 1/2$. |
| Fourier fishing relation | \(\Omega(N/\log N),\ O(N)\) | Sandwiched between $\mathrm{R}_{\varepsilon} = \Omega(N/\log N)$ and $\mathrm{D}^{\mathrm{na}} = N$. |
| Ordered search partial | \(\Theta(n)\) putative | Randomness does not rescue non-adaptivity. Take $k$ uniform on $\{0,\dots,n\}$; a fixed query set of size $t$ leaves the parity determined only when the gap containing $k$ is a singleton, and there are at most $t+1$ singleton gaps, so the algorithm is right with probability at most $\tfrac{t+1}{n+1} + \tfrac12\big(1-\tfrac{t+1}{n+1}\big)$. Forcing this to $\ge 2/3$ gives $t \ge \tfrac{n+1}{3}-1$. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = n$. |
| Tseitin search on an expander relation | \(\Theta(n)\) | Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| Inner product mod 2 total | \(\Theta(n)\) | Between $\mathrm{R} = \Theta(n)$ and $n$. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^3) = \Theta(N)\) | Between $\mathrm{R} = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}} = N$. |
| Sink of a tournament total | \(\Theta(m^2) = \Theta(N)\) putative | Non-adaptively you must read essentially the whole tournament, a full quadratic above $\mathrm{R} = \Theta(\sqrt N)$. Hard distribution: pick $v$ and $u \ne v$ uniformly, orient every edge into $v$ and the rest of the tournament uniformly at random, then flip the edge $uv$ with probability $1/2$. Flipping it destroys the sink and creates a new one only if $u$ is a sink of the sub-tournament, which happens with probability $2^{-(m-2)}$. The unordered pair $\{u,v\}$ is uniform over all $\binom m2$ edges, and flipping the coin is an involution that leaves $x|_S$ unchanged whenever $uv \notin S$, so any fixed $S$ errs with probability $\ge \tfrac12(1 - |S|/\binom m2) - 2^{-(m-2)}$. Hence $|S| = \Omega(N)$, and $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$. |
| Scorpion graphs total | \(\Theta(m^2) = \Theta(N)\) putative | Non-adaptively the scorpion property is evasive up to a constant, a full quadratic above $\mathrm{R} = \Theta(\sqrt N)$. Hard distribution: draw an ordered triple $(s,t,b)$ uniformly and the foot subgraph uniformly, giving a scorpion $G$, then delete the edge $st$ with probability $\tfrac12$ (which isolates $s$, so the result is never a scorpion). Flipping that coin is a measure-preserving involution that does not change $x|_S$ whenever $st \notin S$, so given $x|_S$ the answer is an unbiased coin on that event; since $\{s,t\}$ is uniform over all $\binom m2$ pairs, a fixed $S$ succeeds with probability at most $1 - \tfrac12(1 - |S|/\binom m2)$, forcing $|S| \ge \binom m2/3$. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | Sandwiched between $\mathrm{R} = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}} = N$. |