Let \(T\) be a decision tree on \(n\) Boolean variables, and let \(\rho \) be a restriction on those variables, that is, an assignment giving each variable either a fixed Boolean value or leaving it free. Let \(T|_\rho \) denote the tree obtained by collapsing every branch whose query variable is fixed by \(\rho \) into the corresponding subtree while keeping the unrestricted branches intact, and write \(\mathrm{depth}\) for the maximum length of a path from the root to a leaf. Then

Let \(T\) be a decision tree on \(n\) Boolean variables, let \(\rho \) be a restriction on those variables, and let \(x \in \{ \mathrm{true},\mathrm{false}\} ^n\) be an input. Then evaluating the restricted tree at \(x\) agrees with evaluating \(T\) at the assignment obtained by extending \(\rho \) with \(x\); that is, the restricted tree returns the same bit at \(x\) as \(T\) does at the point that takes each variable’s fixed value under \(\rho \) where \(\rho \) sets it and the value \(x_i\) on the free variables.

Let \(f\) be a Boolean function of \(n\) Boolean variables, and let \(\rho \) be a restriction that fixes some of these variables to Boolean values and leaves the remaining ones free. Write \(f_\rho \) for the restricted function, whose value on an input \(x\) is \(f\) evaluated at the assignment that agrees with \(\rho \) on the fixed coordinates and with \(x\) on the free coordinates. Writing \(D(g)\) for the decision-tree depth of a Boolean function \(g\) — the least depth of a decision tree computing \(g\) — one has \(D(f_\rho ) \le D(f)\).

Let \(f\) be a Boolean function of \(n\) variables, and let \(\rho _1\) and \(\rho _2\) be two restrictions on those variables, each pinning some coordinates to a fixed Boolean value and leaving the rest free. Let \(\rho _1 \circ \rho _2\) be the composed restriction that fixes each coordinate \(i\) to the value assigned by \(\rho _1\) when \(\rho _1\) pins \(i\), and otherwise to the value assigned by \(\rho _2\). For a restriction \(\rho \), write \(f|_{\rho }\) for the function obtained from \(f\) by substituting the fixed values of \(\rho \) and treating the coordinates left free by \(\rho \) as its inputs, and let \(\operatorname {depth}_{\mathrm{DT}}(g)\) denote the least \(d\) for which some decision tree of depth at most \(d\) computes \(g\). Then further restricting along \(\rho _2\) can only lower this depth:

Let \(f : (\mathrm{Fin}\, n \to \mathrm{Bool}) \to \mathrm{Bool}\) be a Boolean function, let \(t \in \mathbb {N}\) be a threshold, and let \(p_1, p_2 \in \mathbb {R}\) satisfy \(0 \lt p_1 \le 1\) and \(0 \lt p_2 \le 1\). For a parameter \(p\), let \(\Pr _p[\, \cdot \, ]\) denote the probability of an event under a Bernoulli(\(p\)) random restriction \(\rho \), in which each variable is left free with probability \(p\) and is otherwise fixed to a constant Boolean value, each of the two values with probability \((1-p)/2\). For a restriction \(\rho \), write \(f_\rho \) for the function of the free coordinates obtained from \(f\) by fixing each set coordinate \(i\) to the value \(\rho (i)\), and let \(D(f_\rho )\) be its decision-tree depth, that is, the least \(d\) for which some decision tree of depth at most \(d\) computes \(f_\rho \). Then