24 Boolean Analysis — Depth3 Switching
24.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.
24.2 Declarations
Let \(f : (\mathrm{Fin}\, n \to \mathbb {F}_2) \to \mathbb {F}_2\) be a Boolean function on \(n\) variables, and let \(\rho _1, \rho _2 : \mathrm{Fin}\, n \to \{ 0, 1, *\} \) be two restrictions, where a coordinate is either fixed to a Boolean value or left free. Write \(\rho _1 * \rho _2\) for their composition, the restriction that on each coordinate takes the value fixed by \(\rho _1\) if there is one and otherwise the value assigned by \(\rho _2\), and for a restriction \(\rho \) write \(f\! \restriction _\rho \) for the function \(x \mapsto f(\rho .\mathrm{extend}\, x)\) obtained by evaluating \(f\) with the fixed coordinates of \(\rho \) substituted and the free coordinates read off from \(x\). Then restricting \(f\) by the composite restriction agrees with restricting first by \(\rho _1\) and then by \(\rho _2\):
Let \(f\) and \(g\) be Boolean functions of \(n\) variables, that is, maps \(\{ 0,1\} ^n \to \{ 0,1\} \), and suppose they agree on every input, so \(f(x) = g(x)\) for all \(x \in \{ 0,1\} ^n\). Then \(f\) and \(g\) have the same decision-tree depth.
Let \(f, g : (\mathrm{Fin}\, n \to \mathbb {F}_2\text{-valued Boolean inputs}) \to \mathrm{Bool}\) be two Boolean functions on \(n\) variables that agree everywhere, \(f(y) = g(y)\) for every input \(y\), and let \(\rho \) be a restriction on \(n\) variables. Then the restricted functions agree as well: writing \(f_\rho (x) = f(\rho .\mathrm{extend}\, x)\) for the restriction of \(f\) by \(\rho \), one has \(f_\rho (x) = g_\rho (x)\) for every \(x : \mathrm{Fin}\, n \to \mathrm{Bool}\).
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\).
Let \(f_1, \dots , f_k\) be Boolean functions on \(n\) variables and let \(\rho \) be a restriction of those variables, and write \(f|_\rho \) for the restriction of a function \(f\) along \(\rho \) (the function \(x \mapsto f(\rho .\mathrm{extend}\, x)\)). Then restricting the pointwise conjunction \(f_1 \wedge \cdots \wedge f_k\) along \(\rho \) agrees, at every point \(x : \mathrm{Fin}\, n \to \mathrm{Bool}\), with the pointwise conjunction of the individually restricted functions \(f_1|_\rho , \dots , f_k|_\rho \).
Fix \(n \ge 1\), and let \(D_1,\dots ,D_{s_2}\) be DNF formulas on \(n\) variables, each of width at most \(w\) with \(w \ge 1\), subject to the two syntactic conditions that within every term any two literals on the same variable coincide (so no term repeats a variable with opposite polarities) and that no term lists the same literal twice. Let \(l \in \mathbb {N}\), and let \(p \in \mathbb {R}\) satisfy \(0 \lt p \le 1/(40w)\) and \(p \le 1\). Draw a Bernoulli\((p)\) random restriction \(\rho \) on the \(n\) variables. Then with probability at least
there exists a CNF formula \(\Psi \) of width at most \(l\) that computes the conjunction of the restricted gates: writing \(D_i\! \restriction _\rho \) for the function \(x \mapsto D_i(\rho .\mathrm{extend}\, x)\) obtained by fixing the coordinates set by \(\rho \) and leaving the free coordinates to \(x\), one has \(\Psi (x) = \bigwedge _{i=1}^{s_2} \bigl(D_i\! \restriction _\rho \bigr)(x)\) for every assignment \(x\).
A clause (a list of literals interpreted as their disjunction) is tautological if it contains two literals on the same variable with opposite signs.
Let \(c\) be a clause on the variables \(x_0,\dots ,x_{n-1}\), that is, a list of literals read as their disjunction, where a literal is a variable together with a sign and evaluates to that variable’s value if positive and to its negation if negated. Suppose \(c\) is tautological: it contains two literals on the same variable with opposite signs. Then for every Boolean assignment \(x \colon \{ 0,\dots ,n-1\} \to \{ \text{true},\text{false}\} \), at least one literal of \(c\) evaluates to \(\mathrm{true}\), so the disjunction of the literals of \(c\) evaluates to \(\mathrm{true}\).
Removes duplicate variables from a clause, keeping the first occurrence of each variable.
Let \(c\) be a clause, that is, a list of literals over the variables \(\{ 0,1,\dots ,n-1\} \), each literal consisting of a variable together with a negation flag. Form the deduplicated clause obtained from \(c\) by keeping, for each variable, only its first occurrence. Then any two literals of this deduplicated clause that share the same variable are in fact the same literal; equivalently, distinct literals of the deduplicated clause have distinct variables.
Let \(c\) be a finite list of literals over the variable set \(\{ 0,1,\dots ,n-1\} \), and form a new list from \(c\) by scanning left to right and discarding every literal whose variable has already appeared, keeping only the first occurrence of each variable. Then this deduplicated list is repetition-free: no literal occurs in it more than once.
Let \(c\) be a clause, that is, a finite list of literals over the variables \(\{ 0,1,\dots ,n-1\} \), and let \(\mathrm{dedup}(c)\) be the clause obtained from \(c\) by retaining, for each variable, only its first occurring literal and discarding every later literal on the same variable. Then the length of \(\mathrm{dedup}(c)\) is at most the length of \(c\).
Let \(c\) be a clause over the variables \(x_0,\dots ,x_{n-1}\) — a list of literals read as their disjunction, where a literal evaluates to \(x_i\) if positive and \(\lnot x_i\) if negated. Suppose \(c\) is not tautological, meaning it contains no two literals on the same variable with opposite signs. Then for every Boolean assignment \(x \colon \{ 0,\dots ,n-1\} \to \{ \mathrm{false},\mathrm{true}\} \), the clause obtained from \(c\) by keeping only the first literal on each variable evaluates to the same truth value as \(c\) itself.
Cleans a CNF by removing all tautological clauses and then deduplicating the variables within each remaining clause.
Let \(\psi \) be a CNF formula over \(n\) Boolean variables — a conjunction of clauses, each clause a disjunction of literals — and let \(x \in \{ 0,1\} ^n\) be an assignment. Form the cleaned formula from \(\psi \) by first deleting every tautological clause (a clause containing two literals on the same variable with opposite signs) and then, within each surviving clause, keeping only the first literal on each variable and discarding later literals on variables already seen. Then the cleaned formula and \(\psi \) evaluate to the same Boolean value on \(x\).
Let \(\psi \) be a CNF formula over \(n\) variables, and form its cleaned version by discarding every tautological clause (one containing two literals on the same variable with opposite signs) and then, within each surviving clause, keeping only the first occurrence of each variable. Writing the width of a CNF formula for the largest number of literals in any of its clauses (and \(0\) for the empty formula), the width of the cleaned formula is at most the width of \(\psi \).
Let \(\psi \) be a CNF formula over \(n\) variables, and let \(\mathrm{clean}(\psi )\) be the formula obtained from \(\psi \) by discarding every tautological clause and then, in each surviving clause, keeping only the first literal on each variable. Then every clause of \(\mathrm{clean}(\psi )\), viewed as a list of literals, contains no repeated literal.
Let \(\psi \) be a CNF formula over the variables \(\mathrm{Fin}\, n\). After cleaning \(\psi \) — that is, after discarding every tautological clause and then deduplicating the variables within each surviving clause — every clause becomes variable-injective: in any clause of the cleaned formula, any two literals sharing the same variable are in fact the same literal.
Let \(\psi \) be a CNF formula in the variables \(x_1,\dots ,x_n\), written as a conjunction of clauses, each clause a disjunction of literals. Then there is a CNF formula \(\psi '\) that computes the same Boolean function as \(\psi \), that is, \(\psi '(x)=\psi (x)\) for every assignment \(x\in \{ 0,1\} ^n\), whose width (the maximum number of literals in any of its clauses) is at most that of \(\psi \), and in which every clause is free of repetition in the strong sense that no literal occurs twice and no two distinct literals share a variable.
Let \(f\colon (\mathrm{Fin}\, n \to \mathbb {F}_2) \to \{ 0,1\} \) be a Boolean function on \(n\) variables, and let \(d\) be a natural number. If the decision-tree depth of \(f\) is at most \(d\), then there is a CNF formula \(\psi \) that computes \(f\) (that is, \(\psi (x) = f(x)\) for every assignment \(x\)) and whose width is at most \(d\), meaning every clause has at most \(d\) literals. Moreover \(\psi \) can be taken clean: within each clause no literal is repeated, and no two literals share the same underlying variable.
Let \(f : (\mathrm{Fin}\, n \to \mathbb {F}_2)\) — more precisely \(f\) a Boolean function on \(n\) variables — have decision-tree depth at most \(d\). Then \(f\) is computed by a DNF formula \(\varphi \) (a disjunction of terms, each term a conjunction of literals) of width at most \(d\), meaning every term of \(\varphi \) contains at most \(d\) literals, such that \(\varphi (x) = f(x)\) for all inputs \(x\). Moreover each term of \(\varphi \) is tidy: no literal is repeated within a term, and no two literals in the same term share a variable (equivalently, within any one term each variable occurs at most once, and with a single fixed polarity).
Fix an integer \(n \ge 1\) and a Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) whose decision-tree depth is at most \(w\), for some integer \(w \ge 1\). Let \(p\) be a real parameter with \(0 \lt p \le 1/(40w)\) (so in particular \(p \le 1\)), and draw a Bernoulli\((p)\) random restriction \(\rho \) on the \(n\) variables: independently, each variable is left free with probability \(p\) and otherwise fixed to \(0\) or to \(1\), each with probability \((1-p)/2\). Then for every \(t \in \mathbb {N}\), the restricted function \(f\restriction \rho \) (that is, \(f\) evaluated on the free coordinates with the remaining coordinates set by \(\rho \)) satisfies
Let \(p_1, p_2 \in (0,1]\), let \(E\) and \(A\) be events on restrictions of \(n\) variables, and let \(\beta \ge 0\). Write \(\Pr _p[\, \cdot \, ]\) for the probability of an event under a Bernoulli(\(p\)) random restriction, and for restrictions \(\rho _1, \rho _2\) let \(\rho _1 \circ \rho _2\) denote their composition (the values fixed by \(\rho _1\), filled in by \(\rho _2\) on the coordinates \(\rho _1\) leaves free). Suppose that for every restriction \(\rho _1\) for which \(A(\rho _1)\) fails, one has \(\Pr _{p_2}[\, E(\rho _1 \circ \rho _2)\, ] \le \beta \). Then
Fix natural numbers \(n\), \(s_2\), and \(l\), a restriction \(\rho _1\) on \(n\) variables, and a family of DNF formulas \(g_0, g_1, \dots , g_{s_2-1}\) on \(n\) variables. For each index \(i\), write \(\tilde g_i\) for the restricted function \(x \mapsto g_i(\rho _1.\mathrm{extend}\, x)\), obtained by evaluating \(g_i\) with the coordinates fixed by \(\rho _1\) set accordingly and the free coordinates supplied by \(x\). Suppose that every \(\tilde g_i\) has decision-tree depth at most \(l\). Then there is a CNF formula \(\Psi \) on \(n\) variables of width at most \(l\) in which each clause has no repeated literal and no two distinct literals sharing a variable, such that for every assignment \(x\),
Let \(g_1,\dots ,g_s\) be DNF formulas in \(n\) Boolean variables, and let \(f : (\mathrm{Fin}\, n \to \mathrm{Bool}) \to \mathrm{Bool}\) be their conjunction, so that \(f(x) = \mathrm{true}\) if and only if \(g_i(x) = \mathrm{true}\) for every \(i\). Fix a restriction \(\rho \) of the \(n\) variables, and write \(h_\rho \) for the restriction of a Boolean function \(h\) by \(\rho \) (the function obtained by fixing each coordinate that \(\rho \) sets and leaving the rest free). Suppose that for every \(i\) the restricted gate \((g_i)_\rho \) has decision-tree depth at most \(l\). Then the restricted function \(f_\rho \) is computed by some CNF formula \(\Psi \) of width at most \(l\) — every clause contains at most \(l\) literals — in which each clause is simple: no literal occurs twice, and any two literals in a clause that share a variable are identical. That is, \(\Psi (x) = f_\rho (x)\) for all \(x\).
Let \(f:\{ 0,1\} ^n\to \{ 0,1\} \) be a Boolean function on \(n\ge 1\) variables, and write \(D(h)\) for the decision-tree depth of a Boolean function \(h\), i.e. the least depth of a decision tree computing it. Suppose \(f\) is the conjunction \(f=g_1\wedge \cdots \wedge g_{s_2}\) of DNF formulas \(g_1,\dots ,g_{s_2}\), meaning \(f(x)=1\) exactly when \(g_i(x)=1\) for every \(i\). Fix a restriction \(\rho _1\) on the \(n\) variables such that each restricted gate satisfies \(D(g_i\! \restriction \! \rho _1)\le l\), where \(l\ge 1\), and let \(t\) be a natural number. Suppose \(0\lt p_2\le \tfrac {1}{40l}\) (so in particular \(p_2\le 1\)), and let \(\rho _2\) be a Bernoulli(\(p_2\)) random restriction — each variable independently left free with probability \(p_2\) and fixed to \(0\) or \(1\) with probability \((1-p_2)/2\) each. Writing \(\rho _1\circ \rho _2\) for the composite restriction that applies \(\rho _1\) first and then \(\rho _2\) on the coordinates left free by \(\rho _1\), we have
Let \(n \ge 1\), and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be the conjunction of \(s_2\) DNF formulas \(g_1, \dots , g_{s_2}\) on \(n\) variables, so that \(f(x) = \mathrm{true}\) exactly when \(g_i(x) = \mathrm{true}\) for every \(i\). Suppose each \(g_i\) has width at most \(w\), where \(w \ge 1\), and that within every term of every \(g_i\) no literal is repeated and no two distinct literals share the same variable. Fix natural numbers \(l \ge 1\) and \(t\), together with real parameters \(p_1, p_2 \in (0,1]\) satisfying \(p_1 \le 1/(40w)\) and \(p_2 \le 1/(40l)\). Writing \(D(g)\) for the decision-tree depth of a Boolean function \(g\) and \(f\restriction _\rho \) for the restricted function \(x \mapsto f(\rho \text{-extension of }x)\), a Bernoulli\((p_1 p_2)\) random restriction \(\rho \) then satisfies
Fix \(n \ge 1\), and let \(f\colon \{ 0,1\} ^n \to \{ 0,1\} \) be the conjunction of \(s_2\) DNF formulas \(g_1,\dots ,g_{s_2}\), so that \(f(x)=1\) if and only if \(g_i(x)=1\) for every \(i\). Assume a width bound \(w \ge 1\) under which each \(g_i\) has width at most \(w\) (every term of every gate has at most \(w\) literals), and assume that within each term of each gate the literals are distinct and no variable occurs twice. Fix integers \(l \ge 1\) and \(t\), and let \(\rho \) be a Bernoulli random restriction with parameter \(\frac{1}{40w}\cdot \frac{1}{40l}\); write \(p_1=\frac{1}{40w}\) and \(p_2=\frac{1}{40l}\). Write \(f\! \restriction _\rho \) for the function obtained by extending each input with the values \(\rho \) fixes, and let \(D(\cdot )\) denote decision-tree depth (the least depth of a decision tree computing the given function). Then the probability that the restricted function has decision-tree depth exceeding \(t\) obeys
Let \(f:\{ 0,1\} ^n\to \{ 0,1\} \) with \(n\ge 1\), and suppose \(f\) is the conjunction of \(s_2\) DNF formulas \(D_1,\dots ,D_{s_2}\), so that \(f(x)=1\) exactly when \(D_i(x)=1\) for every index \(i\); equivalently, \(f\) is computed by a depth-three AND-of-OR-of-AND circuit. Assume each formula \(D_i\) has width at most \(w\) with \(w\ge 1\), and that within every term no literal is repeated and no variable occurs in two opposite polarities, so that a term reads each variable at most once. Fix integers \(l\ge 1\) and \(t\ge 0\) and a real number \(\varepsilon \) satisfying \(s_2\, (1/2)^{l}\le \varepsilon /2\) and \((1/2)^{t}\le \varepsilon /2\), and put \(p_1=1/(40w)\) and \(p_2=1/(40l)\). Draw a Bernoulli random restriction \(\rho \) with parameter \(p_1 p_2\), and write \(f_\rho \) for the restriction of \(f\) by \(\rho \). Then the probability that the decision-tree depth of \(f_\rho \) exceeds \(t\) is at most