19 Boolean Analysis — LMN

19.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.

19.2 Declarations

Lemma 19.1 Lower bound on \(\mathrm{logb}_2(2s/\varepsilon )\)

✓

For \(s \in \mathbb {N}\) with \(0 \lt s\) and \(\varepsilon \in \mathbb {R}\) with \(0 \lt \varepsilon \le 1\), the quantity \(l = \log _2(2s/\varepsilon )\) satisfies \(1 \le l\).

Lemma 19.2 Monotonicity of \(\mathrm{logb}_2(2s/\varepsilon )\) in \(s\)

✓

For \(s \in \mathbb {N}\) with \(0 \lt s\) and \(\varepsilon \in \mathbb {R}\) with \(0 \lt \varepsilon \), we have \(\log _2(2/\varepsilon ) \le \log _2(2s/\varepsilon )\).

Lemma 19.3 Bound \(s \cdot 2^{-l} \le \varepsilon /2\)

✓

For \(s \in \mathbb {N}\) with \(0 \lt s\) and \(\varepsilon \in \mathbb {R}\) with \(0 \lt \varepsilon \), taking \(l = \log _2(2s/\varepsilon )\) gives

\[ s \cdot 2^{-l} \le \frac{\varepsilon }{2}, \]

since \(2^{-l} = \varepsilon /(2s)\).

Lemma 19.4 Value of \(2^{-\mathrm{logb}_2(2/\varepsilon )}\)

✓

For \(\varepsilon \in \mathbb {R}\) with \(0 \lt \varepsilon \),

\[ 2^{-\log _2(2/\varepsilon )} = \frac{\varepsilon }{2}. \]

Lemma 19.5 Iterative circuit reduction bound with Chernoff tails

✓

Let \(c\) be a circuit on \(n\) variables with \(n \gt 0\), depth at most \(d\), size at most \(s\), and fan-in at most \(w\), where \(d \ge 2\) and \(s, w, l \gt 0\). Under a Bernoulli(\(\delta \)) random restriction \(\rho \) with \(\delta = \mathrm{composedDelta}\, w\, l\, d\), the probability that the restricted function has decision-tree depth exceeding \(t\) is bounded by

\[ s \cdot \left(\tfrac {1}{2}\right)^l + \left(\tfrac {1}{2}\right)^t + s \cdot \exp \! \left(-\tfrac {n}{120 w}\right) + s \cdot \exp \! \left(-\tfrac {n}{120 l}\right). \]

The exponential Chernoff tails vanish as \(n \to \infty \).

Theorem 19.6 O’Donnell Lemma 4.28, with tails

✓

Let \(c\) be a circuit on \(n\) variables with \(n \gt 0\), depth at most \(d\), size at most \(s\), and fan-in at most \(w\), where \(d \ge 2\) and \(s, w, l \gt 0\). Fix \(\varepsilon \gt 0\) and naturals \(l, t\) with \(s \cdot \left(\tfrac {1}{2}\right)^l \le \varepsilon /2\) and \(\left(\tfrac {1}{2}\right)^t \le \varepsilon /2\). Then under a Bernoulli(\(\mathrm{composedDelta}\, w\, l\, d\)) restriction \(\rho \),

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

The exponential tails vanish as \(n \to \infty \), giving \(\Pr \le \varepsilon \) asymptotically.