Let \(g\) be a DNF formula on \(n \ge 1\) variables whose width is at most \(w\), where \(w \ge 1\), and suppose that within each term of \(g\) any two literals having the same variable are equal and no literal is repeated. Let \(l\) be a natural number, and let \(p\) be a real number with \(0 \lt p \le 1\) and \(p \le \tfrac {1}{40w}\). Then, under a Bernoulli\((p)\) random restriction \(\rho \), the probability that the restricted function \(g|_\rho \) is computed by no CNF formula of width at most \(l\) is at most

Let \(g\) be a CNF formula on \(n \ge 1\) variables whose width is at most \(w\), where \(w \ge 1\), and suppose that within each clause no two distinct literals share a variable and no literal is repeated. Fix a natural number \(l\) and a real parameter \(p\) with \(0 \lt p \le \tfrac {1}{40w}\), so in particular \(p \le 1\). Then, drawing a Bernoulli\((p)\) random restriction \(\rho \) on the \(n\) variables, the probability that the restricted function \(g|_\rho \) (the function \(x \mapsto g(\rho .\mathrm{extend}\, x)\) on the free coordinates) cannot be computed exactly by any DNF formula of width at most \(l\) is at most

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function, let \(\rho \) be a restriction on the \(n\) variables (fixing some coordinates to Boolean values and leaving the rest free), and write \(f\! \restriction _\rho \) for the restricted function \(x \mapsto f(\rho .\mathrm{extend}\, x)\), obtained by evaluating \(f\) with the fixed coordinates set by \(\rho \) and the free coordinates supplied by \(x\). If \(f\! \restriction _\rho \) has decision-tree depth at most \(l\), then there is a CNF formula \(\psi \) whose every clause contains at most \(l\) literals and which computes \(f\! \restriction _\rho \) on every input, that is, \(\psi (x) = f\! \restriction _\rho (x)\) for all \(x \in \{ 0,1\} ^n\).

Let \(f : (\mathbb {F}_2^{\, n} \to \{ 0,1\} )\) be a Boolean function on \(n\) variables and let \(\rho \) be a restriction that fixes some variables to Boolean values and leaves the others free, so that the restricted function \(f|_\rho \) sends a point \(x\) to the value of \(f\) on the assignment agreeing with \(\rho \) on the fixed coordinates and with \(x\) on the free ones. If \(f|_\rho \) has decision-tree depth at most \(l\) — that is, some decision tree of depth at most \(l\) computes it — then there exists a DNF formula \(\varphi \) whose width (the maximum number of literals in any of its terms) is at most \(l\) and which agrees with \(f|_\rho \) on every input.

Let \(D_0,\dots ,D_{s-1}\) be \(s\) DNF formulas on \(n\) Boolean variables, with \(n \ge 1\), each of width at most \(w\) where \(w \ge 1\), and suppose that in every term of every \(D_i\) each variable occurs at most once (no term repeats a literal, and any two literals of a term on the same variable coincide). Let \(p \in \mathbb {R}\) satisfy \(0 \lt p \le \tfrac {1}{40w}\) and \(p \le 1\). Draw a Bernoulli\((p)\) random restriction \(\rho \), which independently leaves each variable free with probability \(p\) and otherwise fixes it to \(\mathtt{false}\) or \(\mathtt{true}\) each with probability \((1-p)/2\). Then the probability that some restricted formula \(D_i\! \restriction _\rho \) computes a Boolean function of decision-tree depth greater than \(l\) is at most

Let \(n\) and \(l\) be natural numbers, let \(\mathrm{gates}_0,\dots ,\mathrm{gates}_{s-1}\) be a family of DNF formulas in \(n\) variables, and let \(\rho \) be a restriction on the \(n\) variables. Suppose that for every index \(i\) the restricted function \(x \mapsto (\mathrm{gates}_i)(\rho .\mathrm{extend}\, x)\) has decision-tree depth at most \(l\). Then for every index \(i\) there is a CNF formula \(\psi \) of width at most \(l\) that computes this restricted function, that is, \(\psi (x) = (\mathrm{gates}_i)(\rho .\mathrm{extend}\, x)\) for every Boolean assignment \(x\).

Let \(g_1,\dots ,g_{s_2}\) be a family of DNF formulas in \(n\) variables, and suppose \(n \ge 1\). Fix a width bound \(w \ge 1\) and assume each \(g_i\) has width at most \(w\); assume moreover that within every term of every \(g_i\) the literals are pairwise distinct and any two literals on the same variable coincide, so that no variable occurs more than once in a term. Let \(p \in \mathbb {R}\) satisfy \(0 \lt p \le \frac{1}{40w}\) and \(p \le 1\), and draw a random restriction \(\rho \) on the \(n\) variables from the Bernoulli(\(p\)) distribution, in which each variable is independently left free with probability \(p\) and otherwise fixed to \(0\) or \(1\) each with probability \(\frac{1-p}{2}\). Then the probability that some gate \(g_i\) fails to be representable after restriction — that is, that there is an index \(i\) for which the restricted function \(g_i\! \restriction _\rho \) (the value \(x \mapsto g_i(\rho .\mathrm{extend}\, x)\)) is not computed by any CNF formula of width at most \(l\) — is at most

Fix \(n \ge 1\) and let \(g_1, \dots , g_{s_2}\) be \(s_2 \ge 1\) DNF formulas on \(n\) variables (each a disjunction of terms, each term a conjunction of literals), each of width at most \(w \ge 1\), and such that within every term distinct literals involve distinct variables (no variable occurs more than once in a term). Let \(p\) satisfy \(0 \lt p \le 1\) and \(p \le \tfrac {1}{40w}\), and let \(\varepsilon \gt 0\) be such that \(\exp \! \bigl(-\tfrac {np}{3}\bigr) \le \tfrac {\varepsilon }{s_2}\). Then, under a Bernoulli\((p)\) random restriction \(\rho \), the probability that there exists an index \(i\) for which the restricted function \(g_i|_\rho \) admits no CNF formula of width at most \(l\) computing it (equal to it at every input) is at most