21 Boolean Analysis — Circuit Compression
21.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.
21.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).
For a list of terms \(ts\), the folded maximum of their widths is at most \(\ell \) if and only if every term \(t \in ts\) satisfies \(t.\mathrm{width} \le \ell \).
If CNFs \(\psi _1, \dots , \psi _s\) each have width at most \(\ell \), then the CNF obtained by concatenating all their clause lists also has width at most \(\ell \).
For any input \(x\), the value of the concatenated CNF at \(x\) equals the conjunction over all \(\psi \) in the list of \(\psi .\mathrm{eval}\, x\); that is, it holds iff every component CNF holds at \(x\).
If DNFs \(\varphi _1, \dots , \varphi _s\) each have width at most \(\ell \), then the DNF obtained by concatenating all their term lists also has width at most \(\ell \).
For any input \(x\), the value of the concatenated DNF at \(x\) equals the disjunction over all \(\varphi \) in the list of \(\varphi .\mathrm{eval}\, x\); that is, it holds iff some component DNF holds at \(x\).
Let an AND gate have a list of children, each of which computes a function expressible by a CNF of width at most \(\ell \). Then the AND of all children is itself computed by a single CNF of width at most \(\ell \), namely the concatenation of the children’s clause lists. This collapses the AND layer and the CNF layer into one.
Dual to the AND case: if an OR gate has children each expressible by a DNF of width at most \(\ell \), then the OR of all children is computed by a single DNF of width at most \(\ell \), obtained by concatenating the children’s term lists.
For \(s_2\) layer-2 DNF gates of width at most \(w\) (with the usual no-duplicate-variable and nodup hypotheses on terms) and a Bernoulli restriction with parameter \(p \le 1/(40w)\), the probability that some gate fails to admit a width-\(\ell \) CNF representation of its restriction is at most \(s_2 \cdot \left( (1/2)^{\ell } + \exp (-np/3) \right)\).
Under a Bernoulli restriction with \(p \le 1/(40w)\) on \(s_2\) width-\(w\) DNF gates, the probability that every restricted gate has decision-tree depth at most \(\ell \) is at least \(1 - s_2 \cdot \left( (1/2)^{\ell } + \exp (-np/3) \right)\).
For a Bernoulli restriction probability with parameter \(0 \le p \le 1\) and a decidable predicate \(A\) on restrictions, \(\Pr [A] + \Pr [\lnot A] = 1\).
Combining Steps 6 and 7: after a Bernoulli restriction with \(p \le 1/(40w)\) on \(s_2\) width-\(w\) DNF gates, the probability that every restricted gate admits a width-\(\ell \) CNF representation is at least \(1 - s_2 \cdot \left( (1/2)^{\ell } + \exp (-np/3) \right)\), so that the compression of Step 6 applies and the circuit reduces to depth \((d-1)\) with width at most \(\ell \).