Let \(c\) be a Boolean circuit on \(m\) variables — a tree whose leaves are literals and whose internal nodes are AND or OR gates applied to lists of subcircuits — and suppose its depth is \(0\). Then \(c\) is a single leaf: there exists a literal \(l\) such that \(c\) consists of that literal alone.

Let \(g_1,\dots ,g_m\) be DNF formulas on \(n\) Boolean variables, and let \(w\) be a positive integer such that every \(g_i\) has width at most \(w\); assume \(n \ge 1\), and that in each term the literals occupy distinct positions and any two literals sharing a variable are equal (so each variable is queried at most once per term). Let \(c\) be a Boolean circuit on the \(m\) gate-inputs whose depth is \(0\) (hence a single literal), and let \(F\) be the composed Boolean function on \(n\) variables given by \(F(x) = c\bigl(g_1(x),\dots ,g_m(x)\bigr)\). Fix natural numbers \(s\), \(l\), \(t\) with \(l \ge 1\), \(s \ge 1\), \(w \le l\), and \(\mathrm{size}(c) \le s\). Then, for a Bernoulli random restriction \(\rho \) with parameter \(\tfrac {1}{40l}\), the probability that the restriction of \(F\) along \(\rho \) — the function sending \(x\) to \(F\) evaluated with the coordinates fixed by \(\rho \) and the free coordinates read from \(x\) — has decision-tree depth exceeding \(t\) is at most

Let \(n\), \(m\), and \(l\) be natural numbers, let \(\rho _1\) be a restriction on \(n\) variables, and let \(g_1, \dots , g_m\) be DNF formulas on \(n\) variables. For each \(i\), write \(g_i|_{\rho _1}\) for the restricted Boolean function \(x \mapsto g_i\bigl(\rho _1.\mathrm{extend}\, x\bigr)\), that is, \(g_i\) evaluated on the input obtained by setting the fixed coordinates of \(\rho _1\) and reading the free coordinates from \(x\). Suppose that for every \(i\) the decision-tree depth of \(g_i|_{\rho _1}\) is at most \(l\). Then there exist DNF formulas \(g_1', \dots , g_m'\) such that, for every \(i\): the width of \(g_i'\) is at most \(l\); \(g_i'\) computes \(g_i|_{\rho _1}\) on every input; within each term of \(g_i'\) any two literals on the same variable are identical; and no term of \(g_i'\) contains a repeated literal.