23 Boolean Analysis — Circuit Layer Reduction
23.1 Overview
This module proves the core iterative reduction theorem of the LMN argument: under a composed Bernoulli random restriction, a function computed by a bounded-depth, bounded-fan-in circuit has small decision-tree depth with high probability. The proof proceeds by strong induction on the circuit depth \(d\), with a base case (\(d=2\)) handled by the switching lemma and an inductive step (\(d\ge 3\)) that factors the restriction parameter and applies a two-stage argument to the children of the root gate.
23.2 Declarations
For a fan-in bound \(w\), a width parameter \(l\), and a depth \(d\), the composed Bernoulli restriction parameter is
For \(w\gt 0\) and \(l\gt 0\), the composed restriction parameter \(\mathrm{composedDelta}(w,l,d)\) is positive.
For \(w\ge 1\), \(l\ge 1\), and \(d\ge 2\), the composed restriction parameter satisfies \(\mathrm{composedDelta}(w,l,d)\le 1\).
For natural numbers \(w,l\) and depth \(d\ge 3\),
For \(d\ge 3\) and \(l\gt 0\), the composed parameter factors as the \((d-1)\) case times \(1/(40l)\):
A bundle describing the second layer of a circuit over \(n\) variables: a number of gates, a family of DNF formulas indexed by the gates, a common width bound \(\mathrm{width}\gt 0\) such that every gate’s width is at most \(\mathrm{width}\), together with the hypothesis that within each term of each gate distinct literals have distinct variables.
For layer-2 data and a Bernoulli parameter \(p\) with \(0\lt p\le 1/(40\cdot \mathrm{width})\) and \(p\le 1\), the probability that some gate’s restricted function has decision-tree depth greater than \(l\) is at most
For layer-2 data and a Bernoulli parameter \(p\) with \(0\lt p\le 1/(40\cdot \mathrm{width})\) and \(p\le 1\), the probability that it fails that every gate’s restricted function is computed by some width-\(l\) CNF is at most
Given layer sizes summing to at most \(s\), if each per-layer quantity is bounded by \(\mathrm{layerSize}(i)\cdot \alpha \) (with \(\alpha \ge 0\)) and a final term is bounded by \(\beta \), then the total \(\sum _i \mathrm{per\_ layer}(i) + \mathrm{final}\) is at most \(s\cdot \alpha +\beta \).
For a Boolean function \(f\) and restrictions \(\rho _1,\rho _2\), restricting by the composed restriction equals restricting by \(\rho _1\) and then by \(\rho _2\):
Let \(p_1,p_2\in (0,1]\), let \(E\) and \(A\) be predicates on restrictions, and let \(\beta \ge 0\). If for every \(\rho _1\) with \(\neg A(\rho _1)\) the conditional probability \(\Pr _{p_2}[E(\mathrm{composeRestr}\, \rho _1\, \rho _2)]\le \beta \), then
For \(0\le p\le 1\), a Boolean function \(f\), and thresholds \(l_1\le l_2\), the probability that the restricted function exceeds depth \(l_2\) is at most the probability that it exceeds depth \(l_1\).
If \(f\) and \(g\) agree on every input, then the probability that the restriction of \(f\) exceeds depth \(t\) equals the corresponding probability for \(g\).
If \(f\) is computed by a circuit of depth at most \(2\), size at most \(s\), and fan-in at most \(w\), then for a Bernoulli parameter \(p\) with \(0\lt p\le 1/(40w)\) and \(p\le 1\),
The base case (\(d=2\)) of the inductive bound: if \(f\) is computed by a depth-\(2\) circuit of size at most \(s\) and fan-in at most \(w\) (with \(s,w,l\gt 0\) and \(n\gt 0\)), then under the composed restriction parameter \(\mathrm{composedDelta}(w,l,2)\),
For \(0\le p\le 1\), a list of circuits \(\mathit{cs}\), and a predicate \(\mathrm{bad}\) on circuits and restrictions, the probability that some circuit in \(\mathit{cs}\) is bad is bounded by the folded sum of the per-circuit probabilities \(\sum _{c\in \mathit{cs}}\Pr _{p}[\mathrm{bad}\, c]\).
The inductive step: for depth \(d\ge 3\), assuming the bound holds for depth \(d-1\) (the hypothesis \(\mathit{ih}\) applied to each child of the root), a circuit of depth at most \(d\), size at most \(s\), and fan-in at most \(w\) satisfies, under \(\mathrm{composedDelta}(w,l,d)\),
By strong induction on the depth \(d\ge 2\): if \(f\) is computed by a circuit of depth at most \(d\), size at most \(s\), and fan-in at most \(w\) (with \(s,w,l,n\gt 0\)), then under \(\mathrm{composedDelta}(w,l,d)\),
Replacing the coefficient \(s-1\) by \(s\) in the previous bound: under the same hypotheses and the parameter \(\mathrm{composedDelta}(w,l,d)\),
The user-facing form of the iterative reduction: for \(f\) computed by a circuit of depth at most \(d\ge 2\), size at most \(s\), and fan-in at most \(w\), under \(\mathrm{composedDelta}(w,l,d)\),