29 Boolean Analysis — Iterative Reduction

29.1 Overview

This module carries out Steps 8–9 of the LMN argument: it applies the one-step switching/compression mechanism repeatedly across all intermediate circuit layers (reducing depth \(d\) down to depth \(2\)), and combines the per-stage failure probabilities into a single union bound of order \(s\cdot (1/2)^l\). The arithmetic package shows that with \(l=\log _2(2s/\varepsilon )\) the total failure probability is at most \(\varepsilon /2\).

29.2 Declarations

Theorem 29.1 Reduction at subsequent layers

✓

Let \(g_1,\dots ,g_{s_i}\) be width-\(\le l\) DNFs on \(n\) variables (with \(0\lt l\), \(0\lt n\)), and let \(0\lt p\le 1/(40l)\) with \(p\le 1\). Under a Bernoulli\((p)\) random restriction \(\rho \), the probability that some restricted gate fails to be representable by a width-\(\le l\) CNF agreeing with it pointwise is at most \(s_i\cdot \bigl((1/2)^l+\exp (-np/3)\bigr)\). This is the one-step reduction bound applied with width parameter \(l\).

Theorem 29.2 Decision-tree depth at subsequent layers

✓

Under the same hypotheses, a Bernoulli\((p)\) restriction \(\rho \) leaves every one of the \(s_i\) width-\(\le l\) gates with restricted function of decision-tree depth at most \(l\), with probability at least \(1-s_i\cdot \bigl((1/2)^l+\exp (-np/3)\bigr)\). This is the decision-tree-depth form of the one-step bound applied with width \(l\).

Theorem 29.3 Multi-stage failure bound

✓

If over \(m\) stages each failure bound satisfies \(\mathrm{failure\_ bound}(i)\le (\mathrm{layer\_ size}(i))\cdot \alpha \) with \(\alpha \ge 0\), and \(\sum _i \mathrm{layer\_ size}(i)\le s\), then \(\sum _i \mathrm{failure\_ bound}(i)\le s\cdot \alpha \).

Theorem 29.4 Union bound for restriction probabilities

✓

For \(0\le p\le 1\) and finitely many events \(A_0,\dots ,A_{m-1}\) on restrictions, the Bernoulli\((p)\) probability that some \(A_i\) holds is at most the sum of the individual probabilities:

\[ \mathrm{bernoulliRestrProb}\, p\, (\exists i,\, A_i)\le \sum _i \mathrm{bernoulliRestrProb}\, p\, (A_i). \]

Theorem 29.5 Iterative dominant-term bound

✓

For \(\sum _i \mathrm{layer\_ size}(i)\le s\) with \(0\lt s\) and \(0\lt \varepsilon \), setting \(l=\log _2(2s/\varepsilon )\) gives

\[ \sum _i \bigl(\mathrm{layer\_ size}(i)\bigr)\cdot (1/2)^l \le \varepsilon /2 . \]

Theorem 29.6 Two-stage composed union bound

✓

For \(0\le p\le 1\) and \(0\le q\le 1\), and decidable events \(A,B\) on restrictions,

\[ \sum _{\rho _1}\mathrm{bernoulliRestrWeight}\, p\, \rho _1\cdot \mathrm{bernoulliRestrProb}\, q\, (A(\rho _1)\vee B(\rho _2)) \le \mathrm{bernoulliRestrProb}\, p\, A + \mathrm{bernoulliRestrProb}\, q\, B, \]

where the inner event combines \(A\) on the first-stage restriction with \(B\) on the second-stage restriction. This bounds the failure of a composed two-stage Bernoulli restriction by the sum of the two individual stage probabilities.

Theorem 29.7 Abstract iterative reduction

✓

For \(\sum _i \mathrm{layer\_ size}(i)\le s\) with \(0\lt s\) and \(0\lt \varepsilon \), if each per-stage bound satisfies \(\mathrm{per\_ stage\_ bound}(i)\le (\mathrm{layer\_ size}(i))\cdot (1/2)^{\log _2(2s/\varepsilon )}\), then \(\sum _i \mathrm{per\_ stage\_ bound}(i)\le \varepsilon /2\). This packages the union bound over all \(d-2\) iterations as a purely arithmetic consequence of the per-stage bounds.