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

Deterministic query complexity

Minimum worst-case number of queries of a deterministic decision tree computing f.

also written: decision tree complexity, DT(f), D^{dt}(f)

Definition

A deterministic decision tree is a rooted binary tree; each internal node is labelled by an index $i \in [n]$, each edge by a bit, and each leaf by an output. On input $x$ the tree follows the path determined by the bits $x_i$ it reads. $\mathrm{D}(f)$ is the minimum depth of a tree that outputs $f(x)$ on every $x$ in the domain of $f$.

Equivalently, $\mathrm{D}(f)$ is the minimum $d$ such that the adversary can be forced to reveal $f$ after $d$ bits, i.e. the "decision tree depth" of $f$.

Basic facts

  • $\mathrm{D}(f) \le n$ for total $f$, with equality for e.g. $\mathrm{PARITY}_n$.
  • $\mathrm{D}$ is the largest of all the standard measures: every other measure in this zoo is $O(\mathrm{D})$ for total functions (except the size-based ones).
  • $\mathrm{D}(f\circ g) = \mathrm{D}(f)\,\mathrm{D}(g)$ exactly, for total $f,g$ (composition is perfect).

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{D}(f)\). “\(\mathrm{D}(f)\) in terms of it” is the pair with \(\mathrm{D}(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}(f)\) in terms of it It in terms of \(\mathrm{D}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total2,3 partial∞ relation∞ open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total2,2 partial∞ relation∞ open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total4,4 partial∞ relation∞ open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity total2,3 partial∞ relation∞ open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{C}(f)\) Certificate complexity total2,2 partial∞ relation∞ open pair → total1,1 partial1,1 relation1,1 open pair →
\(\deg(f)\) Exact degree total2,3 partial∞ open pair → total1,1 partial1,1 open pair →

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

Known values

FunctionValueNotes
OR total \(n\)
AND total \(n\)
PARITY total \(n\)
MAJORITY total \(n\)
Threshold total \(n\)
Symmetric functions (general) total \(n \text{ (for all but trivial } f)\)
EXACT-HALF total \(n\)
ODD-MAX-BIT total \(n\)
ADDRESS / multiplexer total \(k+1\)
Binary tree navigation total \(k\) The walk reads one variable per level.
TRIBES total \(n\)
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 \(\Theta(N)\) Between $\mathrm{C} = (3k+2)(2k+1)$ and $N = (3k+2)(4k+2)$ -- so between $N/2$ and $N$.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\)
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative Immediate from $\mathrm{D} \ge \mathrm{C} \ge \mathrm{bs}$. Against $N = 2{,}017{,}584^{\,d}$ this is a very small fraction of the input, which is the point: the construction buys a large $\mathrm{bs}$ cheaply in $\lambda$, not in $N$.
Pointer functions total \(\widetilde\Omega(n)\) On a $p\times m$ grid of cells the adversary of [ABBLSS17, Thm 2] leaves the value undetermined after $pm-1$ cell queries, and one cell costs $\lceil\log|\Sigma|\rceil=\Theta(\log n)$ bits, so $\mathrm{D}$ is the input length up to logarithms. This holds for every variant listed below, which is what makes the upper bounds in this table mutually comparable: each $\widetilde O(\cdot)$ entry below is measured on a variant whose $\mathrm{D}$ is still $\widetilde\Omega(n)$. ABBLSS17
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{D}\ge\mathrm{Q}=\widetilde\Omega(n)$, and $\mathrm{D}\le\mathrm{C}^2=\widetilde O(n)$ for a total function.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{D}\ge\mathrm{R}_0\ge\mathrm{Q}$. This is the recorded $\mathrm{D}=\widetilde\Omega(\mathrm{s}^3)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{D}\ge\mathrm{C}_0=\widetilde\Omega(n^2)$ and $\mathrm{D}\le\mathrm{UC}_{\min}^2=\widetilde O(n^2)$ [BHT17]. So the quadratic $\mathrm{C}_0$-vs-$\mathrm{UC}_1$ gap is simultaneously a quadratic $\mathrm{D}$-vs-$\mathrm{UC}_{\min}$ gap, and both are optimal up to logs.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) Squeeze: $\mathrm{D}\ge\mathrm{C}=\Omega(n^2)$ and $\mathrm{D}\le N=n^2$.
Random-indicator gadget total \(n\) Squeeze: $\mathrm{C}\le\mathrm{D}\le n$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(n)\) The adversary of [GPW18, Sec. 2.1] survives $k^2 = \widetilde\Theta(n)$ cell queries; and $\mathrm{D}\le n$ trivially. So this function is maximally hard deterministically, up to logarithms. GPW18
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Squeeze: $\mathrm{D}\ge\mathrm{R}=\widetilde\Omega(n^{2/3})$ and $\mathrm{D}\le\mathrm{UC}_{\min}^2=\widetilde O(n^{2/3})$ [BHT17].
Ambainis' exact-quantum function total \(3^d\) Exactly the input length. $\mathrm{NE}^d(0,\dots,0)=0$ while every weight-one input evaluates to $1$, so all $3^d$ variables are sensitive there. NS94 Ambainis13
FORRELATION partial \(\Theta(n)\)
k-FORRELATION partial \(O(kn)\) Reading all $kn$ bits determines $\Phi_k$; on the other side $\mathrm{D} \ge \mathrm{R} = \widetilde\Omega(n^{1-1/k})$, so for constant $k$ the deterministic complexity is pinned to within $n^{1/k}$. No exact value is recorded in the literature; for $k=2$ see \(\mathrm{forr}\).
Simon's problem partial \(\Theta(2^{n/2})\) putative Both directions are about difference sets. Upper: query $A\cup B$ where $A = \{(u,0^{n/2})\}$ and $B = \{(0^{n/2},v)\}$, which is $2^{n/2+1}-1$ points whose pairwise differences $(u,0)\oplus(0,v)=(u,v)$ exhaust $\mathbb{F}_2^n$; a two-to-one $g$ with shift $s$ must therefore repeat a value inside $A\cup B$, and an injective one never does. Lower: an adversary answering with fresh distinct values survives as long as some shift is unexcluded, and $q$ queries exclude only the $\binom q2$ shifts realised as differences, so $q = \Omega(2^{n/2})$. Note this matches $\mathrm{R}$: the birthday paradox buys randomness nothing here, because covering all $2^n$ differences deterministically is just as cheap.
Deutsch-Jozsa partial \(N/2+1\)
Bernstein-Vazirani partial \(n\)
Unique search partial \(n\) Adversary: answer $0$ to the first $n-1$ queries; the input can still be $0^n$ or $e_i$ at the one unqueried coordinate $i$. Reading all $n$ bits obviously suffices.
Two-or-none search partial \(n-1\) putative Adversary: answer $0$. After $n-2$ queries the two unread coordinates may both be $1$ or both be $0$, and both completions are on the promise. Conversely $n-1$ queries suffice: a $1$ anywhere settles the answer immediately, and if the first $n-1$ are all $0$ then the last coordinate cannot be $1$ alone, since $|x| = 1$ is off the promise.
Marked bit partial \(n\) putative Exactly. Upper: query $y_1,\dots,y_n$, the "is this cell marked $1$" bits. If any is $1$ the answer is $1$; if all are $0$ there are no $1$-marks, and the promise guarantees a mark, so the answer is $0$. Lower: answer $0$ to everything. If some cell has both encoding bits unqueried, the two single-mark inputs there are both still consistent and disagree; so every cell must be touched.
Dense marked bit partial \(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$.
Unstructured search (relation) relation \(n\)
FIND-1 under a density promise relation \(n/2+1\)
Approximate Hamming weight relation \(\Theta(n)\) Reading all $n$ bits is enough, and $\mathrm{D} \ge \mathrm{psD} = \Omega(n)$.
Correlated-string search relation \(\Theta(n)\) putative Sharply $\lceil n/2 + \sqrt n\rceil$. Upper: copy $x$ on the queried coordinates and put $0$ elsewhere. Lower: after $q$ queries the output $y$ is determined, and the adversary sets every unqueried $x_i := 1 - y_i$, forcing distance $n-q$; validity needs $n - q \le n/2 - \sqrt n$.
SearchCNF relation \(\Theta(n)\)· For a random $\Delta$-dense unsatisfiable $k$-CNF. $\mathrm{D}(\mathrm{Search}(\varphi))$ is the minimum depth of a tree-like resolution refutation of $\varphi$ [LNNW95] -- a decision tree solving the search problem, read leaf-to-root, is exactly such a refutation. Random $k$-CNFs require resolution width $\Omega(n)$, hence depth $\Omega(n)$; and $n$ queries trivially suffice. So the $\mathrm{R} = O(1)$ upper bound above is an unbounded $\mathrm{D}$-vs-$\mathrm{R}$ separation, for a total relation. LNNW95 BenSassonWigderson01
Gap-Majority partial \(\Theta(n)\) Independent of $\delta$, and the whole point of the example: $\mathrm{D}$ is unbounded in terms of $\mathrm{R}$ on partial functions. Adversary count: after $q$ queries returning $a$ ones, output $0$ is still consistent iff $a \le n/2-\delta n$ and output $1$ iff $a + (n-q) \ge n/2+\delta n$, so keeping both alive is possible exactly while $q \le (1-2\delta)n$ -- giving $\mathrm{D} = (1-2\delta)n + 1$ up to integrality, and $n$ queries always suffice.
Gap-Majority at constant gap partial \(\Theta(n)\) Exactly $n/2 + 1$ up to integrality, by the adversary count of \(\mathrm{GapMaj}^{\delta}_{n}\) at $\delta = 1/4$: an adversary answering queries can keep both outputs alive for $(1-2\delta)n = n/2$ queries.
Parity-labelled FIND-1 partial \(n/4+1\) putative Exactly. Upper: query $n/4+1$ odd positions; a $1$ among them says $\mathrm{supp}(x) \subseteq \mathrm{Odd}$, and all-zero rules that case out, since $n/4$ ones would then have to fit into the $n/4-1$ odd positions left over. Lower: the adversary answers $0$ throughout. After $q_{\mathrm{odd}}$ odd and $q_{\mathrm{even}}$ even queries both completions survive as long as $n/2 - q_{\mathrm{odd}} \ge n/4$ and $n/2 - q_{\mathrm{even}} \ge n/4$, so the algorithm must spend $n/4+1$ queries inside one parity class before either answer is safe.
Approximate index partial \(\Theta(\sqrt{k\log k})\) putative So this function is not a $\mathrm{D}$-vs-$\mathrm{R}$ separation, which is worth knowing given how hard its $\mathrm{R}$ lower bound works. Lower: $\mathrm{D} \ge \mathrm{R}$. Upper: read the first $q = 4\sqrt{k\log k}$ bits of $a$ and let $b$ agree with them and be $0$ elsewhere, $b'$ agree with them and be $1$ elsewhere. Then $|b-a| + |b'-a| = k-q$, so one of the two is within $(k-q)/2 = k/2 - 2\sqrt{k\log k}$ of $a$ -- inside the ball. Query $x_b$; if it is $2$, query $x_{b'}$, which cannot be. Total $4\sqrt{k\log k}+O(1)$ queries, deterministically. Randomness buys nothing here: it only replaces "read $4\sqrt{k\log k}$ bits and use antipodal guesses" with "read $8\sqrt{k\log k}$ bits and guess at random".
Collision problem partial \(n/2+1\) putative Exactly. Upper: a two-to-one $g$ takes only $n/2$ values, so any $n/2+1$ queries repeat one; a one-to-one $g$ never does. Lower: an adversary answering with fresh values keeps both promises alive for $n/2$ queries, since $k \le n/2$ distinct answers can always be extended to a two-to-one function (put the $k$ queried points in $k$ different pairs).
Element distinctness total \(n\)
Ambainis-Belovs function partial \(O(n)\) Reading all $3n$ variables determines the answer; no matching lower bound is proved, only $\mathrm{D} \ge \mathrm{Q} = \Omega(n^{1/3})$.
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 \(n\) Evasive: $\deg(f) \le \mathrm{D}(f) \le n$ and $\deg = n$ here, so every deterministic tree must read all $n$ bits on some input. This settles the question the previous version of this entry left open, but only as strongly as the $\deg$ computation above.
$k$-distinctness total \(n\) Element-query model.
Triangle finding total \(\binom m2 = n\) Evasive for every $m$: containing $K_k$ is elusive for all $2 \le k \le m$ [Bollobas76]. (Kahn-Saks-Sturtevant gives evasiveness of monotone properties only for prime-power $m$; Chakrabarti-Khot-Shi handle general patterns only along an arithmetic progression.) Bollobas76 CKS02
Recursive Fourier sampling partial \(O(n^{\ell})\) putative Upper: to learn $s_v$ it suffices to learn the $n$ bits $s_v\cdot x$ for $x = e_1,\dots,e_n$, and each of those is $g(s_{vx})$, one recursive call one level down; so $T(\ell) = n\,T(\ell-1)$ with $T(0) = 1$. Lower: $\mathrm{D} \ge \mathrm{R} = n^{\Omega(\log n)}$ at $\ell = \log n$, so at that setting the two meet and $\mathrm{D} = n^{\Theta(\log n)}$. For general $\ell$ only the upper bound is on record.
Welded trees relation \(\tilde\Theta(2^{n/2})\)· Upper $O(n\,2^{n/2})$: Shalev Ben-David, reported in [AaronsonAmbainis18, fn. 5] as $O(\sqrt N\log N)$ with $N = 2^n$ ($O(\sqrt N \log^2 N)$ with Boolean queries), and written out in full as [Liu17thesis, §4.3, Alg. 5] -- breadth-first search the top $\lceil n/2\rceil$ levels, cross using short probe-trees to tell "up" from "down", then search the last $\lfloor n/2\rfloor$ levels. Lower: $\mathrm{D} \ge \mathrm{R} = \Omega(2^{n/2}/n)$. So randomness buys essentially nothing here: $\mathrm{D}$ and $\mathrm{R}$ agree to within $n^2$. AaronsonAmbainis18 Liu17thesis
Local search on the hypercube relation \(\Theta(2^n/\sqrt n)\) [LTT89] characterise $\mathrm{D}$ for every graph in terms of vertex cuts; on the cube the optimum is essentially to query the middle layer. Quoted in this form in [SanthaSzegedy09, §1]. LTT89 SanthaSzegedy09
Local search on the grid relation \(\Theta(k^{d-1})\) Not merely $\tilde\Theta$: the deterministic case was settled before the randomized one. Upper $O(k^{d-1})$ by the divide-and-conquer of Llewellyn-Tovey-Trick: query the $(d-1)$-dimensional middle slab together with the boundary of the current region, take the smallest value seen, and recurse into whichever half contains a strictly smaller neighbour of it -- the region halves each round, so the slab costs form a geometric series. Matching $\Omega(k^{d-1})$ lower bounds are due to [LlewellynTovey93] and, independently, to Althofer and Koschnick (1993). The generic $\mathrm{D} = O(\log N\,(\Delta + s))$ of [SanthaSzegedy09, Thm. 2] with separation number $s([k]^d) = \Theta(k^{d-1})$ recovers the upper bound only up to the $\log$. LTT89 LlewellynTovey93
Fourier fishing relation \(N\) Read everything. Nothing better is possible below $\Omega(N/\log N)$, and nothing better is known at all.
Ordered search partial \(\lceil \log_2(n+1) \rceil\) Exactly. Upper: binary search. Lower: a depth-$T$ tree has at most $2^T$ leaves and must separate all $n+1$ promise inputs.
Tseitin search on an expander relation \(\Theta(n)\) Squeezed between $\mathrm{R} = \Theta(n)$ and the trivial $n$. Equivalently, by [LNNW95], the minimum depth of a tree-like resolution refutation of the Tseitin formula, which is $\Omega(n)$ on an expander. Urquhart87 BenSassonWigderson01 LNNW95
Inner product mod 2 total \(n\) From $\deg = n$ below, and $\deg \le \mathrm{D}$.
Minsky-Papert one-in-a-box total \(N = m^3\) Read-once AND-OR formulas are evasive.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Upper: the standard candidate-elimination argument. Query $m-1$ edges to knock out all but one possible sink (a vertex with an out-edge is not a sink), then spend $m-1$ more verifying the survivor, so $\mathrm{D} \le 2m-3$. Lower: $\mathrm{D} \ge \deg = m-1$.
Scorpion graphs total \(\Theta(m) = \Theta(\sqrt N)\) Upper: at most $6m$ queries. Walk a candidate body around, maintaining a set of vertices known not to be the body; each query eliminates a vertex, so $O(m)$ queries identify $b$ or reject, and $2(m-1)$ more check $s$ and $t$. Lower: $\Omega(m)$, since the answer depends on all $m$ vertices. BvEBL74 LovaszYoung02
Graph connectivity total \(\binom{m}{2} = N\) Evasive for every $m \ge 2$: an adversary can always force all $\binom m2$ queries. One of the earliest properties proved evasive, and the model case for the Aanderaa-Karp-Rosenberg conjecture. Bollobas76 KSS84