16 Boolean Analysis — LMN

16.1 Overview

This module assembles the infrastructure for the LMN theorem (Lemma 4.28 of O’Donnell’s Analysis of Boolean Functions). It provides arithmetic helper lemmas for the \(\mathrm{logb}\)-based parameter choices, an iterative circuit reduction bound carrying explicit Chernoff tails, and the main statement bounding the probability that a random restriction of a bounded-depth circuit has large decision-tree depth.

16.2 Declarations

Lemma 16.1 A logarithmic lower bound

✓

Let \(s \in \mathbb {N}\) be a positive integer and let \(\varepsilon \in \mathbb {R}\) satisfy \(0 \lt \varepsilon \le 1\). Then

\[ 1 \le \log _2\! \left(\frac{2s}{\varepsilon }\right). \]

Lemma 16.2 Monotonicity of a base-2 logarithm in a scale factor

✓

Let \(s \ge 1\) be a positive integer and let \(\varepsilon \gt 0\) be a real number. Then

\[ \log _2\! \left(\frac{2}{\varepsilon }\right) \le \log _2\! \left(\frac{2s}{\varepsilon }\right). \]

Lemma 16.3 Bound on \(s\cdot (1/2)^{\log _2(2s/\varepsilon )}\)

✓

Let \(s\) be a positive integer and let \(\varepsilon \gt 0\) be a real number. Then

\[ s \cdot \left(\tfrac {1}{2}\right)^{\log _2(2s/\varepsilon )} \; \le \; \frac{\varepsilon }{2}, \]

where the exponent \(\log _2(2s/\varepsilon )\) is the base-\(2\) logarithm.

Lemma 16.4 A base-two logarithm identity

✓

For every real number \(\varepsilon \gt 0\),

\[ \left(\tfrac {1}{2}\right)^{\log _2(2/\varepsilon )} = \frac{\varepsilon }{2}, \]

where \(\log _2\) denotes the logarithm to base \(2\).

Lemma 16.5 Iterative circuit reduction bound with Chernoff tails

✓

Let \(c\) be a Boolean circuit on \(n \ge 1\) variables of depth at most \(d\), size at most \(s\), and maximum fan-in at most \(w\), where \(d \ge 2\) and \(s, w, l \ge 1\), and fix a threshold \(t\). Apply a Bernoulli random restriction with parameter

\[ \delta = \frac{1}{40w}\left(\frac{1}{40l}\right)^{d-2}, \]

so that each variable is left free with probability \(\delta \) and otherwise fixed to \(\mathtt{false}\) or \(\mathtt{true}\) with equal probability. Then the probability that the restricted function \(x \mapsto c(\rho .\mathrm{extend}\, x)\) has decision-tree depth exceeding \(t\) satisfies

\[ s\left(\tfrac 12\right)^{l} + \left(\tfrac 12\right)^{t} + s\, \exp \! \left(-\frac{n}{120w}\right) + s\, \exp \! \left(-\frac{n}{120l}\right) \]

as an upper bound.

Theorem 16.6 Switching-lemma depth bound for bounded-depth circuits

✓

Let \(c\) be a Boolean circuit on \(n \ge 1\) variables with depth at most \(d\), size at most \(s\), and maximum fan-in at most \(w\), where \(d \ge 2\) and \(s, w, l \gt 0\). Fix a real number \(\varepsilon \gt 0\) and natural numbers \(l, t\) satisfying \(s \cdot \left(\tfrac {1}{2}\right)^{l} \le \varepsilon /2\) and \(\left(\tfrac {1}{2}\right)^{t} \le \varepsilon /2\), and put

\[ \delta \; =\; \frac{1}{40w}\left(\frac{1}{40l}\right)^{d-2}. \]

Draw a random restriction \(\rho \) on the \(n\) variables by leaving each coordinate free with probability \(\delta \) and otherwise fixing it to a uniformly random Boolean value, all coordinates independent. Let \(c\! \restriction _{\rho }\) denote the restricted function of the free coordinates, obtained by evaluating \(c\) with the coordinates set by \(\rho \) held to their fixed values. Then the probability that \(c\! \restriction _{\rho }\) has decision-tree depth exceeding \(t\)—that is, that no decision tree of depth at most \(t\) computes it—satisfies

\[ \Pr _{\rho }\! \left[\, \operatorname {depth}_{\mathrm{DT}}\! \left(c\! \restriction _{\rho }\right) \gt t \, \right] \; \le \; \varepsilon \; +\; s \cdot \exp \! \left(-\frac{n}{120\, w}\right) \; +\; s \cdot \exp \! \left(-\frac{n}{120\, l}\right). \]