28 Boolean Analysis — Gate Switching
28.1 Overview
This module is Step 4 of the LMN argument: it applies Håstad’s switching lemma to individual gates after a Bernoulli\((p)\) restriction. The key bridge results show that, with high probability, the restriction of a bounded-width \(\mathrm{DNF}\) (or \(\mathrm{CNF}\)) gate has small decision-tree depth and hence admits a small-width \(\mathrm{CNF}\) (or \(\mathrm{DNF}\)) representation, and assemble these into union bounds over all gates of a circuit layer.
28.2 Declarations
Let \(p\in [0,1]\) and let \(A,B\) be predicates on restrictions. If \(A(\rho )\) implies \(B(\rho )\) for every restriction \(\rho \), then
Let \(g\) be a \(\mathrm{DNF}\) of width at most \(w\gt 0\) (with distinct variables per term and no duplicate literals), let \(n\gt 0\), and let \(0\lt p\le \tfrac {1}{40w}\) with \(p\le 1\). Then the probability under a Bernoulli\((p)\) restriction \(\rho \) that \(g|_\rho \) cannot be expressed as a \(\mathrm{CNF}\) of width at most \(l\) is at most
The dual statement. Let \(g\) be a \(\mathrm{CNF}\) of width at most \(w\gt 0\) (with distinct variables per clause and no duplicate literals), let \(n\gt 0\), and let \(0\lt p\le \tfrac {1}{40w}\) with \(p\le 1\). Then the probability under a Bernoulli\((p)\) restriction \(\rho \) that \(g|_\rho \) cannot be expressed as a \(\mathrm{DNF}\) of width at most \(l\) is at most
If the restricted function \(f|_\rho \) has decision-tree depth at most \(l\), then there exists a \(\mathrm{CNF}\) \(\psi \) of width at most \(l\) that computes \(f|_\rho \) on every input.
If the restricted function \(f|_\rho \) has decision-tree depth at most \(l\), then there exists a \(\mathrm{DNF}\) \(\varphi \) of width at most \(l\) that computes \(f|_\rho \) on every input.
Let \(\mathrm{gates}_0,\dots ,\mathrm{gates}_{s-1}\) be \(s\) many \(\mathrm{DNF}\)s, each of width at most \(w\gt 0\) (with distinct variables per term and no duplicate literals), let \(n\gt 0\), and let \(0\lt p\le \tfrac {1}{40w}\) with \(p\le 1\). Then the probability under a Bernoulli\((p)\) restriction \(\rho \) that some gate \(\mathrm{gates}_i\) has \(\mathrm{dtDepth}(\mathrm{gates}_i|_\rho ) \gt l\) is at most
Given a family of \(\mathrm{DNF}\) gates and a restriction \(\rho \) under which every gate satisfies \(\mathrm{dtDepth}(\mathrm{gates}_i|_\rho )\le l\), every gate can be replaced by a \(\mathrm{CNF}\) of width at most \(l\) computing \(\mathrm{gates}_i|_\rho \) on all inputs.
Let \(\mathrm{gates}_0,\dots ,\mathrm{gates}_{s_2-1}\) be the layer-2 \(\mathrm{DNF}\) gates, each of width at most \(w\gt 0\) (with distinct variables per term and no duplicate literals), let \(n\gt 0\), and let \(0\lt p\le \tfrac {1}{40w}\) with \(p\le 1\). Then the probability under a Bernoulli\((p)\) restriction \(\rho \) that some gate fails to admit a width-\(l\) \(\mathrm{CNF}\) representation of \(\mathrm{gates}_i|_\rho \) is at most
Under the same hypotheses as the previous theorem, fix \(\varepsilon \gt 0\) and \(s_2\gt 0\), and suppose \(n\) is large enough that \(\exp \! \bigl(-\tfrac {np}{3}\bigr)\le \tfrac {\varepsilon }{s_2}\). Then the probability under a Bernoulli\((p)\) restriction \(\rho \) that some layer-2 gate fails to admit a width-\(l\) \(\mathrm{CNF}\) representation of \(\mathrm{gates}_i|_\rho \) is at most