18 Boolean Analysis — Circuit Compression
18.1 Overview
This file develops Steps 6 and 7 of the LMN argument: once every layer-2 gate of a depth-\(d\) circuit can be switched to a width-\(\ell \) CNF, two adjacent layers of the same gate type can be merged, producing a depth-\((d-1)\) circuit of width at most \(\ell \). The module supplies the algebraic flattening identities (concatenation of CNF/DNF clause lists preserves width and computes the conjunction/disjunction of the parts), the resulting one-layer compression theorems, and the probabilistic one-step reduction bounds obtained from the switching-lemma union bound under a Bernoulli random restriction.
18.2 Declarations
Flattens a list of lists \([\, \ell _1, \ell _2, \dots \, ]\) into the single list \(\ell _1 \mathbin {+\! \! +} \ell _2 \mathbin {+\! \! +} \cdots \), defined by recursion on the outer list. Used to merge the clause (or term) lists of several CNFs (or DNFs).
Let \(t_1, \dots , t_k\) be a finite list of terms, each a conjunction of literals, and let \(\ell \) be a natural number; write \(w(t)\) for the width of a term (its number of literals). Then the maximum width over the list, taken to be \(0\) when the list is empty, satisfies \(\max _{1 \le i \le k} w(t_i) \le \ell \) if and only if \(w(t) \le \ell \) for every term \(t\) in the list.
Let \(\psi _1, \dots , \psi _s\) be CNF formulas over \(n\) variables, and let \(\ell \) be a natural number such that each \(\psi _i\) has width at most \(\ell \). Then the CNF formula obtained by concatenating all of their clause lists into a single list has width at most \(\ell \).
Let \(\psi _1, \dots , \psi _k\) be CNF formulas over the variables \(\{ 1, \dots , n\} \), and form the single CNF formula obtained by concatenating all of their clause lists into one. Then for every assignment \(x \colon \{ 1,\dots ,n\} \to \{ \text{true},\text{false}\} \), this concatenated formula evaluates to true at \(x\) if and only if every \(\psi _i\) evaluates to true at \(x\).
Let \(\varphi _1, \dots , \varphi _s\) be DNF formulas over \(n\) variables, and let \(\ell \) be a natural number such that each \(\varphi _i\) has width at most \(\ell \) (that is, every term of every \(\varphi _i\) contains at most \(\ell \) literals). Then the DNF formula obtained by concatenating all of their term lists into a single list of terms also has width at most \(\ell \).
Let \(\varphi _1, \dots , \varphi _k\) be DNF formulas over \(n\) variables, and let \(x \in \{ 0,1\} ^n\) be a Boolean assignment. Form the single DNF whose term-list is the concatenation of the term-lists of \(\varphi _1, \dots , \varphi _k\). Then this concatenated formula evaluates to true at \(x\) if and only if at least one of the formulas \(\varphi _i\) evaluates to true at \(x\).
Fix \(n\) and a width bound \(\ell \), and let \(f_1, \dots , f_k\) be Boolean functions on \(n\) variables, each mapping an assignment \(x \in \{ 0,1\} ^n\) to a truth value. Suppose that every \(f_i\) is computed by some CNF formula of width at most \(\ell \), that is, a conjunction of clauses in which each clause has at most \(\ell \) literals. Then their conjunction \(x \mapsto \bigwedge _{i=1}^{k} f_i(x)\) is also computed by a single CNF formula of width at most \(\ell \).
Let \(f_1, \dots , f_m\) be Boolean functions on \(\{ 0,1\} ^n\), and let \(\ell \) be a natural number. Suppose that each \(f_i\) is computed by some DNF formula of width at most \(\ell \), that is, a disjunction of terms in which every term has at most \(\ell \) literals. Then their disjunction \(x \mapsto f_1(x) \lor \cdots \lor f_m(x)\) is also computed by a single DNF formula of width at most \(\ell \).
Fix an integer \(w \ge 1\) and let \(D_1, \dots , D_{s_2}\) be DNF formulas over \(n \ge 1\) Boolean variables, each of width at most \(w\), and suppose that within every term of every \(D_i\) no variable occurs more than once (distinct literals of a term have distinct underlying variables, and no literal is repeated). Let \(0 \lt p \le \tfrac {1}{40w}\) (so in particular \(p \le 1\)), and draw a Bernoulli\((p)\) random restriction \(\rho \) on the \(n\) variables, in which each variable is independently left free with probability \(p\) and otherwise fixed to \(0\) or to \(1\), each with probability \(\tfrac {1-p}{2}\). Then for any target width \(l\), the probability that some restricted gate \(x \mapsto D_i(\rho .\mathrm{extend}\, x)\) fails to be computed by any CNF formula of width at most \(l\) is at most
Fix an integer \(n \ge 1\), let \(w \ge 1\), and let \(g_1, \dots , g_{s_2}\) be \(s_2\) DNF formulas on \(n\) Boolean variables, each of width at most \(w\). Assume that in every term of every \(g_i\) no literal is repeated and no two distinct literals share a variable. Let \(p \in \mathbb {R}\) satisfy \(0 \lt p \le \tfrac {1}{40w}\) (so in particular \(p \le 1\)). Then, under a Bernoulli(\(p\)) random restriction \(\rho \) on the \(n\) variables, the probability that every restricted formula \(x \mapsto g_i(\rho .\mathrm{extend}\, x)\) has decision-tree depth at most \(\ell \) is at least
Fix \(n\) and a parameter \(p\) with \(0 \le p \le 1\), and let \(A\) be a predicate on restrictions of \(n\) variables. Writing \(\Pr [A]\) for the probability that \(A\) holds under a Bernoulli(\(p\)) random restriction, one has
where \(\neg A\) is the predicate that holds exactly for those restrictions on which \(A\) fails.
Let \(g_1,\dots ,g_{s_2}\) be DNF formulas on \(n \ge 1\) variables, each of width at most \(w\), where \(w \ge 1\); assume that in every term of every \(g_i\) any two literals on the same variable coincide (so no term repeats a variable or contains both a literal and its negation) and no literal occurs twice in the term. Fix a natural number \(\ell \) and a real \(p\) with \(0 \lt p \le \tfrac {1}{40w}\) and \(p \le 1\). Then, for a Bernoulli-\(p\) random restriction \(\rho \) of the \(n\) variables,
where \(g_i|_\rho \) is the restriction of \(g_i\) by \(\rho \) and a CNF formula \(\psi \) *computes* \(g_i|_\rho \) when \(\psi \) and \(g_i|_\rho \) agree on every input.