Q The Query Complexity Zoo
\(\mathrm{D}^{\mathrm{na}}(f)\)

Non-adaptive deterministic query complexity

Fewest queries when the whole query set must be fixed in advance.

also written: oblivious decision tree complexity, number of relevant variables (total f)

Definition

The algorithm chooses a set $S \subseteq [n]$ before seeing the input, learns $x|_S$, and must then output $f(x)$. $\mathrm{D}^{\mathrm{na}}(f)$ is the smallest such $|S|$.

For total $f$ this is exactly the number of relevant variables: $S$ works iff $f$ does not depend on any coordinate outside $S$. For partial $f$ it is smaller and less trivial -- $S$ only has to determine $f$ on the promise.

Basic facts

  • $\mathrm{D}(f) \le \mathrm{D}^{\mathrm{na}}(f) \le n$.
  • Adaptivity can save exponentially: $\mathrm{D}(\mathrm{ADDR}) = \log_2 n + 1$ while $\mathrm{D}^{\mathrm{na}}(\mathrm{ADDR}) = n + \log_2 n$, since every data bit is relevant.
  • The other direction is exponential, not unbounded: $\mathrm{D}^{\mathrm{na}}(f) \le 2^{\mathrm{D}(f)}-1$, since a depth-$\mathrm{D}$ tree has at most that many internal nodes and so touches at most that many variables. Binary tree navigation $\mathrm{Nav}_k$ attains it exactly.
  • $\mathrm{D}^{\mathrm{na}}(f) \ge \mathrm{s}(f)$, $\mathrm{bs}(f)$, $\mathrm{deg}(f)$ and every other measure, since all of them are supported on relevant variables.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{D}^{\mathrm{na}}(f)\). “\(\mathrm{D}^{\mathrm{na}}(f)\) in terms of it” is the pair with \(\mathrm{D}^{\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.

Other measure \(\mathrm{D}^{\mathrm{na}}(f)\) in terms of it It in terms of \(\mathrm{D}^{\mathrm{na}}(f)\)
\(\mathrm{D}(f)\) Deterministic query complexity totalexp,exp partialexp,exp relationexp,exp open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity total1,? partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{DTsize}(f)\) Decision tree size total1,1 partial1,1 relation1,1 open pair → totalexp,? partialexp,? relationexp,? derived open pair →
\(\mathrm{C}(f)\) Certificate complexity totalexp,? partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(n\) Every variable is relevant.
AND total \(n\) Every variable is relevant.
PARITY total \(n\)
MAJORITY total \(n\) Every variable is relevant.
Threshold total \(n\)
Symmetric functions (general) total \(n\) A non-degenerate symmetric function depends on every coordinate.
EXACT-HALF total \(n\)
ODD-MAX-BIT total \(n\)
ADDRESS / multiplexer total \(k + 2^k\) Every data bit is relevant, so a non-adaptive algorithm reads the entire table.
Binary tree navigation total \(2^k - 1\) Every variable is relevant: for the node $v$, take the input whose walk reaches $v$ and whose two subtrees below $v$ lead to bottom bits of opposite value. So a non-adaptive algorithm must read all of them, and $\mathrm{D}^{\mathrm{na}} = 2^{\mathrm{D}}-1$ exactly -- the extreme case of the bound $\mathrm{D}^{\mathrm{na}} \le 2^{\mathrm{D}}-1$.
TRIBES total \(n\) Every variable is relevant.
AND-OR tree (depth 2) total \(N = n^2\)
NAND tree (balanced AND-OR formula) total \(N\)
Recursive MAJORITY-of-3 total \(N = 3^d\)
Kushilevitz's function (iterated) total \(N\)
Rubinstein's function total \(N\)
Ambainis-Sun function total \(N = 12k^2+14k+4\) Every variable is relevant, and a non-adaptive algorithm must read every relevant variable.
AND composed with NOT-EXACT-HALF total \(N = n^2\) Every variable is relevant, and a non-adaptive algorithm must read every relevant variable.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative Non-adaptivity only costs more: $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D} \ge \mathrm{bs}$.
Pointer functions total \(\widetilde\Theta(n)\) Squeezed between $\mathrm{D}=\widetilde\Omega(n)$ and the input length $n$.
Cheat-sheet functions total \(\widetilde\Omega(n)\) Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}=\widetilde\Omega(n)$; the ceiling is again the input length $n^{10+o(1)}$ rather than anything in the $n$-scale.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^2)\) Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$; the ceiling is the arity $\widetilde\Theta(n^4)$.
Gilmer-Saks-Srinivasan functions total \(n^2\) Squeeze: $\mathrm{D}\le\mathrm{Dna}\le N=n^2$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(n)\) Squeezed between $\mathrm{D}=\widetilde\Omega(n)$ and the input length $n$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{D}\le\mathrm{Dna}\le n$.
FORRELATION partial \(\Theta(n)\) Between $\mathrm{D} = \Theta(n)$ and the trivial $2n$.
k-FORRELATION partial \(O(kn)\) The whole input, fixed in advance; and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
Simon's problem partial \(\Theta(2^{n/2})\) putative The $A\cup B$ query set above is fixed in advance, so the deterministic upper bound is already non-adaptive; and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
Deutsch-Jozsa partial \(N/2+1\) putative Adaptivity is worthless here: any fixed $N/2+1$ positions contain a $0$ and a $1$ of every balanced input (which has exactly $N/2$ of each), so reading them decides. And $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
Bernstein-Vazirani partial \(n\) putative The spanning set $e_1,\dots,e_n$ is fixed in advance, and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$.
Marked bit partial \(n\) putative Adaptivity buys nothing: the $y_b$ algorithm is already non-adaptive, and the lower bound above needs one query per cell whatever the order.
Dense marked bit partial \(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}$.
Unstructured search (relation) relation \(n\) Adaptivity buys nothing: $\mathrm{D} = n$ already, and reading the whole input non-adaptively also costs $n$.
FIND-1 under a density promise relation \(n/2+1\) putative A fixed set of $n/2+1$ positions must contain a $1$ (a promise input has at most $n/2$ zeros), and a fixed set of $n/2$ positions can be entirely zero. So adaptivity is worth nothing on the deterministic side either -- all the power is in the coins.
Approximate Hamming weight relation \(\Theta(n)\) Between $\mathrm{D}=\Theta(n)$ and the trivial $n$.
Correlated-string search relation \(\Theta(n)\) putative The deterministic algorithm above is non-adaptive, and the adversary argument does not care about adaptivity.
SearchCNF relation \(n\) Every variable is relevant, so a non-adaptive algorithm reads the whole assignment.
Gap-Majority partial \(\Theta(n)\) Between $\mathrm{D} = \Theta(n)$ and the trivial $n$; the adversary count for $\mathrm{D}$ never used adaptivity anyway.
Gap-Majority at constant gap partial \(\Theta(n)\) Between $\mathrm{D}$ and $n$; the adversary count never used adaptivity.
Parity-labelled FIND-1 partial \(n/4+1\) putative The same count as $\mathrm{D}$, which never used adaptivity: a fixed set missing $n/4$ odd and $n/4$ even positions is consistent with both answers, and a fixed set of $n/4+1$ odd positions decides. So all the power here is in the coins, not in adaptivity.
Approximate index partial \(\Theta(\sqrt{k\log k})\) putative Adaptivity is worth nothing: read the first $4\sqrt{k\log k}$ bits of $a$ and query both antipodal completions $x_b$ and $x_{b'}$ at once -- one of them is inside the ball. And $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. Note the lemma "$\mathrm{D}^{\mathrm{na}} = n$ for functions depending on all variables" does not apply here: with $\mathrm{s} = 0$, no single coordinate is relevant within the promise.
Collision problem partial \(n/2+1\) putative The same $n/2+1$ positions, fixed in advance.
Element distinctness total \(n\) Every symbol is relevant, so a non-adaptive algorithm reads all of them -- which here costs nothing, since $\mathrm{D}=n$ anyway.
Ambainis-Belovs function partial \(O(n)\) The same $3n$ positions, fixed in advance.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{D}$.
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) At least $\mathrm{D}$.
Surjectivity total \(n\) Every bit is relevant -- permute the list so that the slot in question holds a uniquely-occurring value, and flipping any of its bits changes the answer -- so for a total function the non-adaptive cost is the full $n$. Consistent with $\mathrm{D} = \mathrm{D}^{\mathrm{na}} = n$: adaptivity buys nothing here.
$k$-distinctness total \(n\) Every symbol is relevant, so a non-adaptive algorithm reads all of them; $\mathrm{D} = n$ anyway.
Triangle finding total \(\binom m2 = n\) Every edge is relevant, so a non-adaptive deterministic algorithm reads the whole adjacency matrix -- which costs nothing extra, since the property is evasive.
Recursive Fourier sampling partial \(O(n^{\ell})\) putative Adaptivity buys nothing: the $O(n^{\ell})$ deterministic algorithm of the $\mathrm{D}$ entry is already non-adaptive. Its query set is fixed in advance -- the $n^{\ell}$ leaves $(e_{i_1},\dots,e_{i_\ell})$ whose every path component is a standard basis vector -- and the recursion $s_v\cdot e_i = g(s_{v e_i})$ then reconstructs every secret bottom-up. So $\mathrm{D} \le \mathrm{D}^{\mathrm{na}} \le n^{\ell}$, and at $\ell = \log n$ both are $n^{\Theta(\log n)}$.
Welded trees relation \(\Theta(4^n)\) putative Adaptivity is not a convenience here, it is the whole problem: $\mathrm{D}^{\mathrm{na}}/\mathrm{D} = \tilde\Theta(2^{3n/2})$. A non-adaptive algorithm must fix its query names in advance knowing only $\pi(\mathrm{ENTRANCE})$, and the $2^{n+2}-2$ real names are a $2^{-n+2}$ fraction of the $2^{2n}$ name space. Upper: query all $9\cdot 2^{2n}$ (name, colour) pairs and reconstruct the graph. Lower: let $S$ be the set of names queried. The transcript reveals $\pi(\mathrm{EXIT})$ only if $\mathrm{EXIT}$ or one of its $\le 3$ neighbours lies in $S$; if not, and if some name outside $S$ is unused, swapping $\pi(\mathrm{EXIT})$ with that name leaves the transcript unchanged and the required output different. So $|S| \ge 2^{2n} - 2^{n+2} - 1$.
Local search on the hypercube relation \(2^n\) putative Every cell -- that is, the whole table, $N = 2^n$ -- and the loss against $\mathrm{D} = \Theta(2^n/\sqrt n)$ is only the $\sqrt n$. Suppose the fixed query set $S$ omits the cell $u$ and let $f$ agree on $S$ with the Hamming distance to $u$. If $f(u) = 0$ then $u$ is the unique local minimum, while if $f(u)$ is huge the local minima are exactly the $n$ neighbours of $u$; the transcript is the same in both cases and the required output differs, so $S$ must be everything.
Local search on the grid relation \(k^d = N\) putative Every cell, for every $d \ge 1$, so non-adaptivity is catastrophic already at $d = 2$ where $\mathrm{D} = \Theta(k)$. If the fixed query set $S$ omits the cell $u$, let $f$ agree on $S$ with the $\ell_1$ distance to $u$: when $f(u) = 0$ the unique local minimum is $u$, and when $f(u)$ is huge the local minima are exactly the neighbours of $u$. Same transcript, different required output.
Fourier fishing relation \(N\) Trivially, since $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D} = N$ and reading the whole truth table is non-adaptive. Adaptivity is worth nothing here, which is the mirror image of \(\mathrm{WT}_n\).
Ordered search partial \(n\) putative A fixed query set $S$ tells you only which gap of $S$ the boundary $k$ falls into, i.e. an interval of candidate $k$; the $|S|+1$ intervals must all be singletons to determine the parity, and there are $n+1$ candidates, so $|S| \ge n$. Adaptivity is worth an exponential factor here -- the largest possible, since $\mathrm{D}^{\mathrm{na}} \le n$ always.
Tseitin search on an expander relation \(n\) Between $\mathrm{D} = \Theta(n)$ and the trivial $n$.
Inner product mod 2 total \(n\) Every variable is relevant, so non-adaptively you read all of them.
Minsky-Papert one-in-a-box total \(N = m^3\) Every variable is relevant.
Sink of a tournament total \(N = \binom m2\) Every edge is relevant.
Scorpion graphs total \(\binom{m}{2} = N\) putative Every pair $uv$ is sensitive somewhere -- take the scorpion with sting $u$, tail $v$ -- so a fixed query set that omits $uv$ fails to separate that scorpion from its neighbour. Hence all $N$ bits must be read in advance, against $\mathrm{D} = \Theta(\sqrt N)$. (The $\mathrm{D}^{\mathrm{na}} = N$ half is the generic fact that a non-adaptive algorithm must read every relevant variable; what is special here is how small $\mathrm{D}$ is.) \(\mathrm{Nav}_k\) pushes the same phenomenon to an exponential gap; the scorpion is the natural graph-theoretic instance.
Graph connectivity total \(\binom{m}{2} = N\) Every pair is relevant, so a non-adaptive algorithm reads everything. Here that is no loss at all: $\mathrm{D}=N$ already, connectivity being evasive.