27 Boolean Analysis — Depth3 Switching
27.1 Overview
This module formalizes the switching argument for depth-3 circuits in normal form: a depth-3 AND-of-OR-of-AND circuit is written as the AND of \(s_2\) width-\(w\) DNF gates. It provides the one-step depth-3 to depth-2 compression, the two-stage switching bound under a composed random restriction, and the resulting circuit-reduction probability bounds, together with the CNF-cleaning machinery (tautology removal and per-clause variable deduplication) needed to put restricted gates into normal form.
27.2 Declarations
For a Boolean function \(f\) and restrictions \(\rho _1,\rho _2\), restricting \(f\) by the composition \(\rho _1 \circ \rho _2\) equals first restricting by \(\rho _1\) and then by \(\rho _2\): \(\mathrm{restrictFn}\, f\, (\mathrm{composeRestr}\, \rho _1\, \rho _2) = \mathrm{restrictFn}\, (\mathrm{restrictFn}\, f\, \rho _1)\, \rho _2\).
If two Boolean functions \(f\) and \(g\) agree at every input, then they have the same decision-tree depth: \(\mathrm{dtDepth}\, f = \mathrm{dtDepth}\, g\).
If two Boolean functions \(f\) and \(g\) agree at every input, then for any restriction \(\rho \) their restrictions agree pointwise: \(\mathrm{restrictFn}\, f\, \rho \, x = \mathrm{restrictFn}\, g\, \rho \, x\) for all \(x\).
The pointwise conjunction of a list of Boolean functions: the empty list yields the constant \(\mathrm{true}\) function, and \(f :: fs\) evaluates at \(x\) to \(f(x)\) AND the value of the list \(fs\) at \(x\).
Restricting the pointwise AND of a list of functions equals the pointwise AND of the restricted functions: for all \(x\), \(\mathrm{restrictFn}\, (\mathrm{listAnd}\, fs)\, \rho \, x = \mathrm{listAnd}(fs.\mathrm{map}\, (\lambda f.\ \mathrm{restrictFn}\, f\, \rho ))\, x\).
Given \(s_2\) DNF gates each of width \(\le w\) (with \(w \gt 0\), non-degenerate and duplicate-free terms) and \(n \gt 0\), for any \(0 \lt p \le 1/(40w)\) the Bernoulli\((p)\) random restriction satisfies, with probability at least \(1 - s_2\bigl((1/2)^l + \exp (-np/3)\bigr)\), that there exists a CNF \(\Psi \) of width \(\le l\) whose evaluation equals the AND of the restricted gates. This is the depth-3 to depth-2 compression step.
A clause (a list of literals interpreted as their disjunction) is tautological if it contains two literals on the same variable with opposite signs.
If a clause \(c\) is tautological, then for every assignment \(x\) the disjunction of its literals evaluates to \(\mathrm{true}\).
Removes duplicate variables from a clause, keeping the first occurrence of each variable.
In \(\mathrm{dedupClauseVars}\, c\), any two literals with the same variable are equal; that is, the resulting clause has pairwise distinct variable indices.
The list \(\mathrm{dedupClauseVars}\, c\) has no duplicate literals.
The length of \(\mathrm{dedupClauseVars}\, c\) is at most the length of \(c\).
If a clause \(c\) is not tautological, then for every assignment \(x\) the disjunction of the literals of \(\mathrm{dedupClauseVars}\, c\) has the same value as the disjunction of the literals of \(c\).
Cleans a CNF by removing all tautological clauses and then deduplicating the variables within each remaining clause.
For every assignment \(x\), the cleaned CNF \(\mathrm{cleanCNF\_ D3}\, \psi \) evaluates to the same value as \(\psi \).
The width of \(\mathrm{cleanCNF\_ D3}\, \psi \) is at most the width of \(\psi \).
Every clause of \(\mathrm{cleanCNF\_ D3}\, \psi \) has no duplicate literals.
In every clause of \(\mathrm{cleanCNF\_ D3}\, \psi \), any two literals sharing the same variable are equal.
For any CNF \(\psi \) there exists a CNF \(\psi '\) of width \(\le \) that of \(\psi \), evaluating identically to \(\psi \) on every input, with no duplicate literals in any clause and with each clause variable-injective. Hence every CNF can be cleaned to satisfy the switching lemma hypotheses.
If a Boolean function \(f\) has decision-tree depth \(\le d\), then there is a CNF \(\psi \) of width \(\le d\) that computes \(f\), with all clauses nodup and variable-injective.
If a Boolean function \(f\) has decision-tree depth \(\le d\), then there is a DNF \(\varphi \) of width \(\le d\) that computes \(f\), with all terms nodup and variable-injective.
For any function \(f\) with decision-tree depth \(\le w\) (with \(w \gt 0\), \(n \gt 0\)) and any \(0 \lt p \le 1/(40w)\), the Bernoulli\((p)\) restriction satisfies \(\Pr _\rho [\mathrm{dtDepth}(\mathrm{restrictFn}\, f\, \rho ) \gt t] \le (1/2)^t + \exp (-np/3)\). This is the switching lemma stated at the level of functions rather than formulas.
Let \(0 \lt p_1,p_2 \le 1\), let \(E\) be an event on restrictions and \(A\) a “failure” event, and let \(\beta \ge 0\). If for every \(\rho _1\) with \(\lnot A(\rho _1)\) the conditional probability \(\Pr _{p_2}[E(\mathrm{composeRestr}\, \rho _1\, \rho _2)] \le \beta \), then \(\Pr _{p_1 p_2}[E] \le \Pr _{p_1}[A] + \beta \).
If each restricted gate \(\mathrm{restrictFn}\, (\mathrm{gates}\, i).\mathrm{eval}\, \rho _1\) has decision-tree depth \(\le l\), then there is a CNF \(\Psi \) of width \(\le l\), with nodup and variable-injective clauses, whose evaluation equals the AND over all gates of their restricted evaluations.
Suppose \(f\) is the AND of the gates (\(f(x) = \mathrm{true}\) iff every gate is true at \(x\)) and each restricted gate has decision-tree depth \(\le l\). Then there is a CNF \(\Psi \) of width \(\le l\), with nodup and variable-injective clauses, whose evaluation equals \(\mathrm{restrictFn}\, f\, \rho _1\).
Suppose \(f\) is the AND of the gates and, under the first-stage restriction \(\rho _1\), each restricted gate has decision-tree depth \(\le l\) (with \(l \gt 0\), \(n \gt 0\)). Then for any \(0 \lt p_2 \le 1/(40l)\) the second-stage Bernoulli\((p_2)\) restriction satisfies \(\Pr _{\rho _2}[\mathrm{dtDepth}(\mathrm{restrictFn}\, f\, (\mathrm{composeRestr}\, \rho _1\, \rho _2)) \gt t] \le (1/2)^t + \exp (-np_2/3)\).
Let \(f\) be the AND of \(s_2\) DNF gates each of width \(\le w\) (with \(w,l \gt 0\), non-degenerate and duplicate-free terms, \(n \gt 0\)). For \(0 \lt p_1 \le 1/(40w)\) and \(0 \lt p_2 \le 1/(40l)\), the composed Bernoulli\((p_1 p_2)\) restriction satisfies
For a depth-3 circuit in normal form (AND of \(s_2\) width-\(w\) DNF gates, with \(w,l \gt 0\), \(n \gt 0\)), under the composed Bernoulli\((\mathrm{composedDelta}\, w\, l\, 3) = \mathrm{Bernoulli}(1/(40w) \cdot 1/(40l))\) restriction, writing \(p_1 = 1/(40w)\) and \(p_2 = 1/(40l)\),
For a depth-3 circuit in normal form, if \(l\) and \(t\) are chosen so that \(s_2 (1/2)^l \le \varepsilon /2\) and \((1/2)^t \le \varepsilon /2\), then under the composed Bernoulli\((\mathrm{composedDelta}\, w\, l\, 3)\) restriction (with \(p_1 = 1/(40w)\), \(p_2 = 1/(40l)\)),
The exponential tails vanish as \(n \to \infty \), so the bound is \(\le \varepsilon \) asymptotically.