Fix positive integers \(n\) and \(l\), and let \(g_1,\dots ,g_{s_i}\) be DNF formulas on \(n\) variables, each of width at most \(l\), and each in reduced form: no term repeats a literal, and within a term any two literals on the same variable coincide, so every variable occurs at most once in each term. Let \(p\) be a real parameter with \(0 \lt p \le 1\) and \(p \le \tfrac {1}{40\, l}\). Draw a Bernoulli(\(p\)) random restriction \(\rho \) of the \(n\) variables, which independently leaves each variable free with probability \(p\) and otherwise fixes it to \(0\) or \(1\) each with probability \((1-p)/2\). Then the probability that some restricted gate fails to be computed by a narrow CNF — that is, for some \(i\) there is no CNF formula \(\psi \) of width at most \(l\) satisfying \(\psi (x) = g_i(\rho .\mathrm{extend}\, x)\) for every assignment \(x\) — is at most

Fix an integer \(n \ge 1\) and a positive integer \(l\), and let \(\phi _1, \dots , \phi _s\) be DNF formulas on \(n\) Boolean variables, each of width at most \(l\) and each written so that no variable occurs more than once in any single term — that is, no term repeats a literal, and no term contains two literals on the same variable. Let \(p \in \mathbb {R}\) satisfy \(0 \lt p \le \tfrac {1}{40 l}\) (so in particular \(p \le 1\)). Then a Bernoulli\((p)\) random restriction \(\rho \) on the \(n\) variables satisfies, with probability at least

that for every \(i\) the restricted function \(x \mapsto \phi _i\) evaluated on the coordinates left free by \(\rho \) (with the fixed coordinates set by \(\rho \)) has decision-tree depth at most \(l\).

Let \(\alpha \ge 0\), let \(s \in \mathbb {N}\), and consider \(m\) stages with layer sizes \(\ell _0, \ldots , \ell _{m-1} \in \mathbb {N}\) whose total does not exceed \(s\), i.e. \(\sum _{i} \ell _i \le s\). Suppose real numbers \(b_0, \ldots , b_{m-1}\) satisfy \(b_i \le \ell _i\, \alpha \) for every \(i\). Then \(\sum _{i} b_i \le s\, \alpha \).

Fix a parameter \(p \in \mathbb {R}\) with \(0 \le p \le 1\), and let \(A_0, \dots , A_{m-1}\) be finitely many events on restrictions of \(n\) variables. Under a Bernoulli(\(p\)) random restriction, the probability that at least one of the events \(A_i\) occurs is at most the sum of the probabilities of the individual events:

where \(\mathbb {P}_p[\cdot ]\) denotes the Bernoulli event probability at parameter \(p\).

Fix a natural number \(m\) and layer sizes \(\ell _0,\dots ,\ell _{m-1}\in \mathbb {N}\), and let \(s\in \mathbb {N}\) with \(s\gt 0\) bound their total, \(\sum _{i} \ell _i \le s\). Let \(\varepsilon \gt 0\) be a real number. Under these hypotheses the intended conclusion is that, on setting \(l=\log _2(2s/\varepsilon )\), the total weighted contribution is controlled by \(\varepsilon /2\), namely \(\sum _{i} \ell _i\, (1/2)^{l}\le \varepsilon /2\); however, the formal statement leaves both the value \(l\) and the conclusion as placeholders, so it asserts no mathematical claim beyond these hypotheses.

Fix \(n\), and let \(p,q\) be real parameters with \(0\le p\le 1\) and \(0\le q\le 1\). For a parameter \(r\) write \(w_r(\rho )\) for the Bernoulli weight of a restriction \(\rho \) on \(n\) variables at parameter \(r\), and write \(\mathbb {P}_r[E]\) for the Bernoulli event probability of a predicate \(E\) on restrictions at parameter \(r\). Then for any two predicates \(A\) and \(B\) on restrictions of \(n\) variables,

where the inner sum ranges over all restrictions \(\rho _1\) on \(n\) variables and, for each fixed \(\rho _1\), the predicate \(\rho _2 \mapsto A(\rho _1)\lor B(\rho _2)\) holds at a second-stage restriction \(\rho _2\) exactly when \(A\) holds at \(\rho _1\) or \(B\) holds at \(\rho _2\).

Let \(m\) be a natural number and let \(\ell _0,\dots ,\ell _{m-1}\) be natural numbers (the layer sizes) whose sum is at most a positive integer \(s\). Fix a real number \(\varepsilon \gt 0\), and suppose that \(b_0,\dots ,b_{m-1}\) are real numbers satisfying

Then \(\sum _{i} b_i \le \varepsilon /2\).