Decision tree rank
The "Strahler number" of a decision tree: how much branching, rather than how much depth, the tree needs.
also written:
Ehrenfeucht-Haussler rank, Prover-Delayer game value
Definition
For a decision tree $T$, define $\mathrm{rank}$ bottom-up: a leaf has rank $0$; an internal node whose children have ranks $r_1 \ge r_2$ has rank $r_1$ if $r_1 > r_2$ and $r_1 + 1$ if $r_1 = r_2$. So the rank counts how deep the nested branching goes, ignoring long "caterpillar" paths. $\mathrm{rank}(f)$ is the minimum rank of a decision tree computing $f$.
Equivalently it is the value of the Prover-Delayer game on $f$: the Delayer scores a point whenever the Prover's next query is one the Delayer may answer either way.
Basic facts
- $\mathrm{rank}(f) \le \mathrm{D}(f)$, and $\mathrm{rank}$ can be exponentially smaller: $\mathrm{rank}(\mathrm{OR}_n) = 1$ while $\mathrm{D}(\mathrm{OR}_n) = n$.
- A tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{rank}(f) \le \log_2 \mathrm{DTsize}(f)$.
- A tree of rank $r$ and depth $d$ has at most $\sum_{i\le r}\binom{d}{i} \le (ed/r)^r$ leaves, so $\mathrm{DTsize}(f) \le n^{O(\mathrm{rank}(f))}$ -- this is the Ehrenfeucht-Haussler learning bound [EhrenfeuchtHaussler89].
- $\mathrm{rank}(f) \le \mathrm{rank}(T)$ for the size-optimal tree $T$; rank and size are the pair of measures that behave well under composition of read-once formulas.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{rank}(f)\). “\(\mathrm{rank}(f)\) in terms of it” is the pair with \(\mathrm{rank}(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 | \(1\) | The "first $1$" tree is a caterpillar -- every internal node has a leaf child -- and rank $0$ would mean $f$ is constant. |
| AND total | \(1\) | Caterpillar tree: query the bits in order and stop at the first $0$. |
| PARITY total | \(n\) | Both children of every node of every tree for $\oplus_n$ compute a parity of the remaining variables, so the two ranks are equal at every level and the rank climbs by one each time. |
| MAJORITY total | \((n+1)/2\) putative | Prover-Delayer: until one side has $(n+1)/2$ votes the Delayer may answer either way, scoring a point each time; the counting tree attains it. |
| Threshold total | \(\min\{k,\; n-k+1\}\) putative | Prover--Delayer: if the Delayer always defers, the Prover must drive the transcript to $k$ ones or to $n-k+1$ zeros before the value is fixed, and scores nothing on the way, so the Delayer banks $\min\{k,\,n-k+1\}$ points. Conversely $r(n,k) := \min\{k,\,n-k+1\}$ satisfies the rank recursion for the tree that queries $x_1$ first: its children have ranks $r(n-1,k-1)$ and $r(n-1,k)$, which differ by one when $k \ne n-k+1$ and are equal to $r(n,k)-1$ when $k = n-k+1$. Recovers $\mathrm{rank}(\mathrm{OR}) = 1$ and $\mathrm{rank}(\mathrm{MAJ}) = (n+1)/2$; against $\mathrm{D} = n$ this is an unbounded rank-vs-depth gap already inside the threshold family. |
| EXACT-HALF total | \(n/2 + 1\) putative | Prover-Delayer: the value stays undetermined until one of the two counts reaches $n/2+1$, and until then the Delayer may defer on every query, so she scores $n/2+1$; the counting tree, which stops as soon as either count passes $n/2$, attains it. Same value as \(\mathrm{MAJ}_n\) -- exactness costs nothing in rank, only in depth on the $1$-side. |
| ODD-MAX-BIT total | \(1\) putative | The optimal tree is a caterpillar: query $x_n$, then $x_{n-1}$, and so on, stopping at the first $1$ -- whose index immediately gives the answer. Every internal node therefore has a leaf child, so the rank is $1$ (and it cannot be $0$, as $\mathrm{OMB}$ is not constant). Against $\mathrm{D} = n$ this is the maximum possible rank-vs-depth gap, matching \(\mathrm{OR}_n\). It also explains $\mathrm{DTsize} = n+1$. |
| ADDRESS / multiplexer total | \(k+1\) putative | Upper: $\mathrm{rank} \le \mathrm{D} = k+1$. Lower: in the Prover--Delayer game the Delayer defers on every query, so the game lasts at least $\mathrm{C}_{\min}$ rounds; in general $\mathrm{C}_{\min}(f) \le \mathrm{rank}(f)$, and here $\mathrm{C}_{\min} = k+1$. So $\mathrm{ADDR}$ has full rank: none of its depth is caterpillar. |
| Binary tree navigation total | \(k\) putative | Prover-Delayer: whenever the Prover queries a node the walk has just reached, both answers are still live, so the Delayer scores; the Prover must resolve all $k$ walk nodes, and off-walk queries are answered for free. That gives $\mathrm{rank} \ge k$, and the complete depth-$k$ walk tree has rank exactly $k$. So $\mathrm{rank} = \mathrm{D}$ here -- the opposite extreme from \(\mathrm{OR}_n\), where $\mathrm{rank} = 1$ and $\mathrm{D} = n$. |
| TRIBES total | \(\Theta(n/\log n)\)· putative | Equal to the number of tribes $s$. Write $h(m,r)$ for the rank of $\mathrm{AND}_m \vee G$ with $\mathrm{rank}(G) = r$ on disjoint variables: $h(1,r) = r$ (the $\mathrm{AND}_1$ variable has a constant branch) and $h(m,r) = r+1$ for $m \ge 2$, since querying a tribe variable gives branches of rank $r$ and $r$ or $r+1$. Iterating over the $s$ tribes from $\mathrm{rank}(\mathrm{AND}_w) = 1$ gives $s$. Checked by hand at $w = s = 2$, where the rank is $2$. |
| AND-OR tree (depth 2) total | \(n = \sqrt N\) putative | Upper: read the blocks left to right, and inside a block read bits until a $1$ appears. The block subtree has rank $1$, and grafting rank-$r$ subtrees onto the leaves of a rank-$1$ tree gives rank $\le r+1$, so $\mathrm{rank}_j = \mathrm{rank}_{j+1} + 1$ and the whole tree has rank $n$. Lower: $\mathrm{C}_{\min} = n$ here and $\mathrm{C}_{\min} \le \mathrm{rank}$ (a Delayer who always defers survives $\mathrm{C}_{\min}$ rounds). So $\mathrm{rank} = \mathrm{C}_{\min} = \mathrm{C} = n$ while $\mathrm{D} = n^2$. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(N)\) putative | Between $N/4$ and $N$. Lower, by the composing Prover--Delayer bound $\mathrm{rank}(f\circ g^n) \ge \mathrm{D}(f)(\mathrm{C}_{\min}(g)-1)$: the Delayer defers the first $\mathrm{C}_{\min}(g)-1$ queries in each block, then commits to that block's value and forces it, and the game cannot end before $\mathrm{D}(f)$ blocks have reached their commitment. A single NAND gate has $\mathrm{C}_{\min} = 1$ and gives nothing, but writing $f_d = f_{d-2}\circ f_2$ with $\mathrm{C}_{\min}(f_2) = 2$ gives $\mathrm{rank} \ge 2^{d-2} = N/4$. Exact minimisation gives $1,2,3,6,11$ at $d = 1,\dots,5$. So the NAND tree has essentially full rank even though $\mathrm{C}_{\min} = \Theta(\sqrt N)$. |
| Recursive MAJORITY-of-3 total | \(\Theta(N)\) putative | Between $N/3$ and $N$. Upper: $\mathrm{rank}\le\mathrm{D}$. Lower, by a Prover--Delayer argument that composes: $\mathrm{rank}(f\circ g^n) \ge \mathrm{D}(f)\,(\mathrm{C}_{\min}(g)-1)$. Indeed the Delayer defers the first $\mathrm{C}_{\min}(g)-1$ queries inside each block -- so few bits can never determine that block's value -- and only then commits to the value the block will take, answering afterwards so as to force it. The order in which blocks reach that commitment is an adversary play against $f$, and the game cannot end until the completed blocks alone determine $f$, so at least $\mathrm{D}(f)$ blocks reach commitment, each paying $\mathrm{C}_{\min}(g)-1$ points. With $f = \mathrm{MAJ}_3^{\circ(d-1)}$ and $g = \mathrm{MAJ}_3$ ($\mathrm{D}(f) = 3^{d-1}$, $\mathrm{C}_{\min}(g) = 2$) this gives $\mathrm{rank} \ge 3^{d-1} = N/3$. Exact minimisation gives $2, 5, 14$ at $d = 1,2,3$, i.e. $(3^d+1)/2$. Recursive majority therefore has essentially full rank, while $\mathrm{C}_{\min} = N^{0.63}$ -- the generic $\mathrm{C}_{\min}\le\mathrm{rank}$ bound is far from tight here. |
| Kushilevitz's function (iterated) total | \(\Theta(N)\) putative | Between $N/2$ and $N$. Upper: $\mathrm{rank}\le\mathrm{D}=N$. Lower, by a Prover--Delayer argument that composes: $\mathrm{rank}(f\circ g^n) \ge \mathrm{D}(f)\,(\mathrm{C}_{\min}(g)-1)$. The Delayer defers the first $\mathrm{C}_{\min}(g)-1$ queries inside each block -- so few bits can never determine that block's value -- and only then commits to the value the block will take, answering afterwards so as to force it. The order in which blocks reach that commitment is an adversary play against $f$, and the game cannot end until the completed blocks alone determine $f$, so at least $\mathrm{D}(f)$ blocks reach commitment, each paying $\mathrm{C}_{\min}(g)-1$ points. Here $\mathrm{C}_{\min}(K) = 4$ and $\mathrm{D}(K^{\circ k-1}) = 6^{k-1}$, so $\mathrm{rank} \ge 3\cdot 6^{k-1} = N/2$. Kushilevitz's function therefore has full rank up to a factor $2$: none of its depth is caterpillar, in contrast with $\mathrm{C}_{\min} = N^{0.77}$. |
| Rubinstein's function total | \(\Theta(\sqrt N)\) putative | Between $n$ and $2n$. Lower: $\mathrm{C}_{\min} \le \mathrm{rank}$ and $\mathrm{C}_{\min} = n$. Upper: the gadget has $\mathrm{rank}(g) = 2$ (query $y_1$; whichever way it goes, either the residual is a conjunction of literals or the same problem with one pair fewer -- verified exactly for $n \le 8$), and evaluating the blocks in turn grafts the remaining tree onto the $0$-leaves of a rank-$2$ tree, so $\mathrm{rank} \le 2n$. |
| Ambainis-Sun function total | \(\Theta(k) = \Theta(\sqrt N)\) putative | Lower: $\mathrm{C}_{\min} \le \mathrm{rank}$ gives $3k+2$. Upper: the gadget has $\mathrm{rank}(g) = 2$ (computed exactly for $k = 1,2$), and reading the blocks in turn grafts the remaining tree onto the $0$-leaves, so $\mathrm{rank} \le 2(3k+2)$. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2) = \Theta(N)\) putative | Upper $\mathrm{rank} \le \mathrm{D} = \Theta(n^2)$. Lower: in the Prover--Delayer game the Delayer defers on the first $n/2$ queries inside each block, scoring a point each time -- no $n/2$ bits of a block can decide $\overline{\mathrm{EH}}_n$, whose $\mathrm{C}_{\min}$ is $n/2+1$ -- and then answers the rest of that block so that it evaluates to $1$. The top $\mathrm{AND}_n$ is then undetermined until all $n$ blocks have been visited, so the Delayer scores $n\cdot n/2 = N/2$. Note this is much stronger than the generic $\mathrm{C}_{\min} \le \mathrm{rank}$, which only gives $\sqrt N$. |
| Pointer functions total | \(\widetilde\Omega(\sqrt n)\) | Variant $f_{2m,m}$: a Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{rank}\le\mathrm{D}=\widetilde O(n)$. |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(n)\) | A Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=n$; the ceiling is $\mathrm{rank}\le\mathrm{D}=\Theta(n^2)$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n)\) | A Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{rank}\le\mathrm{D}=\widetilde\Theta(n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/3})\) | A Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=\widetilde\Omega(n^{1/3})$; the ceiling is $\mathrm{rank}\le\mathrm{D}=\widetilde\Theta(n^{2/3})$. |
| Ambainis' exact-quantum function total | \(\Omega(2.3028^d)\) | A Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=\Omega(2.3028^d)$; the ceiling is $\mathrm{rank}\le\mathrm{D}=3^d$. |
| FORRELATION partial | \(\Theta(n)\) | A tree of rank $r$ has a leaf at depth $\le r$, so $\mathrm{C}_{\min} \le \mathrm{rank} \le \mathrm{D}$; both ends are $\Theta(n)$. |
| k-FORRELATION partial | \(O(kn)\) | At most $\mathrm{D} = O(kn)$. |
| Deutsch-Jozsa partial | \(2\) putative | Query $x_1, x_2, \dots$ and stop as soon as two different values appear (answer "balanced") or $N/2+1$ equal values appear (answer "constant"). Each of the root's two subtrees is a caterpillar, hence of rank $1$, so the tree has rank $2$; and $\mathrm{rank} \ge \mathrm{C}_{\min} = 2$. So rank sees none of the $\Theta(N)$ depth -- all of it is caterpillar. |
| Bernstein-Vazirani partial | \(n\) putative | Squeezed between $\mathrm{C}_{\min} = n$ and $\mathrm{D} = n$. Unlike \(\mathrm{DJ}_n\), where the depth is all caterpillar and $\mathrm{rank} = 2$, here every query genuinely branches. |
| Unique search partial | \(1\) putative | "Query $x_1$; if $1$ output $1$, else query $x_2$; ..." is a caterpillar -- every internal node has a leaf child -- so its rank is $1$, against $\mathrm{D} = n$. |
| Two-or-none search partial | \(1\) putative | "Query $x_1$; if $1$ output $1$, else query $x_2$; ..." is a caterpillar, so its rank is $1$ -- and it is correct precisely because one observed $1$ already forces $|x| = 2$. |
| Marked bit partial | \(1\) putative | "Query $y_1$; if $1$ output $1$, else query $y_2$; ..." is a caterpillar -- every internal node has a leaf child -- so its rank is $1$, against $\mathrm{D} = n$. |
| Dense marked bit partial | \(1\) putative | "Query $y_1$; if $1$ output $1$, else query $y_2$; ..." is a caterpillar -- every internal node has a leaf child -- so its rank is $1$, against $\mathrm{D} = n/2+1$. |
| Unstructured search (relation) relation | \(1\) putative | The tree "query $x_1, x_2, \dots$, stop at the first $1$" is a caterpillar -- every internal node has a leaf child -- so it has rank $1$, and rank $0$ would mean no queries at all. So $\mathrm{rank}=1$ against $\mathrm{D}=n$, exactly as for \(\mathrm{OR}_n\). |
| FIND-1 under a density promise relation | \(1\) putative | The optimal tree "query $x_1, x_2, \dots$ and stop at the first $1$" is a caterpillar, so its rank is $1$; and rank $0$ means a constant answer. A Delayer in the Prover--Delayer game scores nothing here because the Prover's query is always one the adversary is happy to answer $0$. |
| Approximate Hamming weight relation | \(\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)$. |
| SearchCNF relation | \(\Theta(n)\)· putative | Decision-tree rank for $\mathrm{Search}(\varphi)$ is exactly the value of the Pudlak--Impagliazzo Prover--Delayer game, and a Delayer scoring $p$ points forces tree-like resolution size $\ge 2^{p}$. Random $\Delta$-dense $k$-CNFs admit a Delayer strategy scoring $\Omega(n)$ points, and $\mathrm{rank} \le \mathrm{D} = \Theta(n)$. |
| Gap-Majority partial | \(\Theta(n)\) putative | Squeezed between $\mathrm{C}_{\min}$ and $\mathrm{D}$, both $\Theta(n)$: with every certificate of full length there is no caterpillar structure to exploit. |
| Gap-Majority at constant gap partial | \(\Theta(n)\) putative | Between $\mathrm{C}_{\min}$ and $\mathrm{D}$: with every certificate of full length there is no caterpillar structure to exploit. |
| Parity-labelled FIND-1 partial | \(1\) putative | That caterpillar has rank $1$ -- one child of every internal node is a leaf -- and rank $0$ means a constant answer. |
| Approximate index partial | \(O(\sqrt{k\log k})\) | At most $\mathrm{D}$; at least $1$. |
| Collision problem partial | \(O(n)\) | At most $\mathrm{D} = n/2+1$. |
| Ambainis-Belovs function partial | \(O(n)\) | At most $\mathrm{D} = O(n)$. |
| Yamakawa-Zhandry problem relation | \(\Omega(n)\) | A tree of rank $r$ has a leaf at depth $\le r$, so $\mathrm{rank} \ge \mathrm{C}_{\min} = n$. Nothing better follows from the recorded values, since only a lower bound on $\mathrm{D}$ is known. |
| Fourier fishing relation | \(\Omega(N/\log N),\ O(N)\) putative | A depth-$d$ decision tree of rank $r$ has at most $\sum_{i \le r}\binom di \le (d+1)^r$ leaves [EhrenfeuchtHaussler89]. Here $d \le N$ and, by the $\mathrm{DTsize}$ row, every tree has at least $2^{N/2}$ leaves, so $(N+1)^r \ge 2^{N/2}$ and $r = \Omega(N/\log N)$. Upper: $\mathrm{rank} \le \mathrm{D} = N$ (\(\mathrm{rank}(f)\) vs \(\mathrm{D}(f)\)). Note that the whole $\log N$ of the window is the crudeness of $(d+1)^r$, not any slack in the certificate bound. EhrenfeuchtHaussler89 |
| Ordered search partial | \(1\) putative | The cheapest illustration in the zoo of rank ignoring caterpillars. Linear search -- query $x_1$; if it is $1$ output $k=0$, otherwise query $x_2$, and so on -- is a comb: every internal node has a leaf for one child, so the rank never rises above $1$, while the depth is $n$. Hence $\mathrm{rank} = 1$ against $\mathrm{D} = \lceil\log_2(n+1)\rceil$: the size-optimal and depth-optimal trees are different trees, and the rank-optimal one is neither. ($\mathrm{rank} \ge 1$ because $\mathrm{OS}_n$ is not constant.) |
| Tseitin search on an expander relation | \(\Omega(n/\log n),\ O(n)\) putative | A depth-$d$ tree of rank $r$ has at most $\sum_{i\le r}\binom di \le (d+1)^r$ leaves [EhrenfeuchtHaussler89]. Here $d \le n$ and $\mathrm{DTsize} = 2^{\Omega(n)}$ [Urquhart87], so $(n+1)^r \ge 2^{\Omega(n)}$ and $r = \Omega(n/\log n)$; the ceiling is $\mathrm{rank} \le \mathrm{D} = \Theta(n)$ (\(\mathrm{rank}(f)\) vs \(\mathrm{D}(f)\)). In Prover-Delayer terms the Delayer scores $\Omega(n/\log n)$ points on an expander Tseitin formula. EhrenfeuchtHaussler89 Urquhart87 |
| Inner product mod 2 total | \(n/2\) putative | Upper: in the natural tree, the node handling index $i$ has one child of rank $r$ (the branch $x_i=0$) and one of rank $r+1$ (the branch $x_i=1$, which then splits on $y_i$), so the rank grows by exactly $1$ per index: $m = n/2$. Lower: a Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}(f) \ge \mathrm{C}_{\min}(f) = m$. A clean factor-$2$ gap below $\mathrm{D} = n$: half of IP's depth is caterpillar. |
| Minsky-Papert one-in-a-box total | \(m = N^{1/3}\) putative | Upper: read the boxes in order, and inside a box read bits until a $1$ appears. A box subtree is a caterpillar, of rank $1$, and grafting a rank-$r$ tree onto the leaves of a rank-$1$ tree gives rank $\le r+1$, so the rank climbs by exactly one per box. Lower: a Delayer who always defers survives $\mathrm{C}_{\min} = m$ rounds. So $\mathrm{rank} = m$ against $\mathrm{D} = m^3$ -- almost all of the depth is caterpillar, and it lives inside the boxes. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: a Delayer who always defers survives $\mathrm{C}_{\min} = m-1$ rounds, and $\mathrm{rank} \le \mathrm{D} = O(m)$. Nothing about SINK is caterpillar-shaped. |
| Scorpion graphs total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: a Delayer who always defers survives $\mathrm{C}_{\min} = m-1$ rounds, so $\mathrm{rank} \ge m-1$, and $\mathrm{rank} \le \mathrm{D} = O(m)$. So the scorpion decision tree is genuinely branching, not a caterpillar -- unlike \(\mathrm{OR}_n\), whose $\mathrm{D}$ is also large while $\mathrm{rank} = 1$. |