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.
The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |