Let \(w\) be a positive integer fan-in bound, let \(l \gt 0\) be a width parameter, and let \(d\) be any depth. Then the composed Bernoulli restriction parameter

is strictly positive.

Let \(w \ge 1\) be a natural number, let \(l \ge 1\) be a real number, and let \(d \ge 2\) be a natural number. Then the composed Bernoulli restriction parameter satisfies

Write \(\delta (w,l,d) = \dfrac {1}{40w}\left(\dfrac {1}{40l}\right)^{d-2}\) for the composed restriction parameter, with fan-in bound \(w\), width parameter \(l\), and depth \(d\). For natural numbers \(w\) and \(l\) and any depth \(d \ge 3\),

Fix a fan-in bound \(w\), a width parameter \(l \gt 0\), and a depth \(d \ge 3\), and for these values write \(\delta (w,l,d)\) for the composed Bernoulli restriction parameter, namely \(\delta (w,l,d) = \frac{1}{40w}\left(\frac{1}{40l}\right)^{d-2}\). Then decreasing the depth by one removes a single factor of \(1/(40l)\):

Let \(f : (\mathrm{Fin}\, n \to \mathrm{Bool}) \to \mathrm{Bool}\) be a Boolean function on \(n\) variables, and let \(\rho _1, \rho _2\) be two restrictions on those variables, each fixing some coordinates to Boolean values and leaving the rest free. Write \(\rho _1 \circ \rho _2\) for their composition, the restriction that on each coordinate uses the value fixed by \(\rho _1\) when there is one and otherwise the value assigned by \(\rho _2\), and for a restriction \(\rho \) write \(f\! \restriction _\rho \) for the function obtained from \(f\) by fixing the coordinates set by \(\rho \) and evaluating on the remaining free coordinates. Then restricting \(f\) by the composition \(\rho _1 \circ \rho _2\) gives the same function as first restricting \(f\) by \(\rho _1\) and then restricting the function \(f\! \restriction _{\rho _1}\) by \(\rho _2\):

Fix a parameter \(p\) with \(0 \le p \le 1\), a Boolean function \(f : (\mathrm{Fin}\, n \to \mathrm{Bool}) \to \mathrm{Bool}\), and thresholds \(l_1 \le l_2\). Under a Bernoulli(\(p\)) random restriction \(\rho \) on the \(n\) variables, the probability that the restricted function \(x \mapsto f(\rho .\mathrm{extend}\, x)\) has decision-tree depth strictly greater than \(l_2\) is at most the probability that it has decision-tree depth strictly greater than \(l_1\).

Fix a real parameter \(p\), a threshold \(t \in \mathbb {N}\), and two Boolean functions \(f, g : (\mathrm{Fin}\, n \to \mathrm{Bool}) \to \mathrm{Bool}\) that agree at every input, so \(f(x) = g(x)\) for all \(x\). Draw a Bernoulli(\(p\)) random restriction \(\rho \) of the \(n\) variables, write \(h_\rho \) for the restricted function obtained from a Boolean function \(h\) under \(\rho \), and let \(D(\cdot )\) denote decision-tree depth. Then

i.e. the two functions assign the same probability to the event that the restricted function has decision-tree depth strictly greater than \(t\).

Let \(f\colon \{ 0,1\} ^n\to \{ 0,1\} \) be a Boolean function on \(n\ge 1\) variables that is computed by some Boolean circuit of depth at most \(2\), size at most \(s\), and fan-in at most \(w\), where \(w\ge 1\). Fix a real parameter \(p\) with \(0\lt p\le \tfrac {1}{40w}\) (so in particular \(p\le 1\)), and draw a random restriction \(\rho \) in which each of the \(n\) variables is, independently, left free with probability \(p\) and otherwise fixed to the value \(0\) or to the value \(1\), each with probability \(\tfrac {1-p}{2}\). Write \(f_\rho \) for the restriction of \(f\) by \(\rho \) (the function \(x\mapsto f\) evaluated at the assignment agreeing with \(\rho \) on its fixed coordinates and with \(x\) on the free ones), and let \(D(g)\) denote the least depth of a decision tree computing a function \(g\). Then for every \(t\in \mathbb {N}\),

Let \(f\colon \{ 0,1\} ^n\to \{ 0,1\} \) be a Boolean function on \(n\ge 1\) variables, let \(s,w,l\ge 1\) be positive integers, let \(t\ge 0\), and suppose \(f\) is computed by a Boolean circuit of depth at most \(2\), size at most \(s\), and fan-in at most \(w\). Draw a random restriction \(\rho \) that leaves each variable free independently with probability \(p=\tfrac {1}{40w}\) and otherwise fixes it to \(0\) or \(1\), each with probability \(\tfrac {1-p}{2}\). Writing \(D(g)\) for the least depth of a decision tree computing a Boolean function \(g\), and \(f\! \restriction _\rho \) for the function obtained from \(f\) by substituting the fixed values of \(\rho \) and keeping the free coordinates as inputs, the probability that the restricted function is hard to compute by a shallow decision tree satisfies

Fix a parameter \(p\) with \(0 \le p \le 1\), and consider a Bernoulli\((p)\) random restriction on \(n\) variables, under which each variable is independently left free with probability \(p\) and fixed to each of the two Boolean values with probability \((1-p)/2\). Let \(c_1, \dots , c_m\) be a list of Boolean circuits on \(n\) variables, and for each circuit \(c\) let \(\mathrm{bad}(c, \cdot )\) be a predicate on restrictions. Then the probability that some circuit in the list is bad is at most the sum of the individual probabilities:

where each term is the probability, under the same random restriction, that the corresponding predicate holds.

Let \(f:\{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function on \(n \ge 1\) variables, and fix natural numbers \(d,s,w,l,t\) with \(d \ge 3\) and \(s,w,l \ge 1\). Suppose \(f\) is computed by a Boolean circuit of depth at most \(d\), size at most \(s\), and maximum fan-in at most \(w\). For parameters \(w,l\) and a depth \(e\), write \(\delta _e = \frac{1}{40w}\left(\frac{1}{40l}\right)^{e-2}\) for the composed restriction parameter; let \(D(g)\) denote the decision-tree depth of a Boolean function \(g\), and let \(g|_\rho \) denote its restriction by a restriction \(\rho \). Assume the following inductive hypothesis: for every Boolean function \(g\) on \(n\) variables and every integer \(s' \ge 1\), if \(g\) is computed by a circuit of depth at most \(d-1\), size at most \(s'\), and maximum fan-in at most \(w\), then under a Bernoulli random restriction \(\rho \) with parameter \(\delta _{d-1}\),

Then under a Bernoulli random restriction \(\rho \) with parameter \(\delta _{d}\),