Analysis of Boolean Functions at CMU - Lecture 8: Linial--Mansour--Nisan Theorems

Analysis of Boolean Functions at CMU - Lecture 8: Linial--Mansour--Nisan Theorems

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Ryan O'Donnell 👥 14K 📅 July 7, 2017 ⏱ 74 min 👁 850 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

Linial-Mansour-NisanSwitching Lemmarandom restrictionsFourier concentrationAC0 circuits

Summary

This is the eighth lecture in Ryan O’Donnell’s course on Analysis of Boolean Functions at Carnegie Mellon. The lecture focuses on proving the Linial-Mansour-Nisan (LMN) theorems, which establish Fourier concentration bounds for functions computed by constant-depth circuits (AC0). The instructor begins by reviewing DNFs and CNFs, then introduces constant-depth circuits and their parameters (size, width, depth). The main goal is to prove that for any function computed by a size-s, depth-d circuit, its Fourier spectrum is ε-concentrated up to degree O((log s)^{d-1} log(1/ε)). The proof relies on Håstad’s Switching Lemma, which states that under a random restriction, a DNF becomes a shallow decision tree with high probability. The lecture also derives corollaries: AC0 circuits are learnable in quasi-polynomial time, and any constant-depth circuit computing parity on more than half the inputs must have exponential size. The instructor also proves a stronger Fourier concentration result for DNFs, improving the dependence on ε from 1/ε to log(1/ε). The lecture is highly technical, with detailed proofs and calculations.

165 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a rigorous and self-contained proof of the LMN theorems, which are fundamental results in computational complexity and Fourier analysis of Boolean functions. The argumentation is solid: the instructor clearly states the theorems, introduces the necessary tools (random restrictions, Håstad’s Switching Lemma), and carefully derives the concentration bounds. The proof of the key lemma (Lemma *) is detailed, and the instructor also discusses the tightness of the results and mentions improvements by Håstad. The lecture also highlights the applications of the theorems, such as learning algorithms for AC0 circuits and lower bounds for parity, which adds to its value.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, based on the instructor’s textbook and original research papers. The instructor explicitly references the LMN paper (1989) and Håstad’s Switching Lemma (1987). The title accurately reflects the content, as the lecture is entirely devoted to the LMN theorems. The sources cited in the description include the course website and the free textbook, which are reliable and directly relevant. The lecture does not contain any advertising or sponsored content.

189 words

Title / Content Match

The title accurately reflects the content: the lecture focuses on the Linial--Mansour--Nisan theorems and their proofs.

Quality & Reliability

9/10

Lecture by a recognized expert (Ryan O'Donnell) at Carnegie Mellon, based on a well-established textbook and research literature. The content is mathematically rigorous, with proofs and references to original papers (LMN 1989, Håstad's Switching Lemma).

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

  • Analysis of Boolean Functions (textbook) — The textbook contains the same theorems and proofs, providing a consistent reference.

Contribution & Novelties

This lecture provides a clear and detailed exposition of the LMN theorems, which are central to the analysis of Boolean functions and circuit complexity. The instructor’s pedagogical approach, building from DNFs to general constant-depth circuits, makes the material accessible. The lecture also highlights the power of random restrictions and Håstad’s Switching Lemma. For further exploration, one can look into the original LMN paper, Håstad’s thesis, and the concept of Fourier concentration in other settings.

Pour aller plus loin :

  • Linial, Mansour, Nisan (1989) - Constant depth circuits, Fourier transform, and learnability — Original paper introducing the LMN theorems.
  • Håstad’s Switching Lemma (Wikipedia) — Overview of the key lemma used in the proof.
  • AC0 (Wikipedia) — Complexity class of constant-depth circuits.
  • Fourier analysis of Boolean functions (Wikipedia) — General background on the topic.

132 words

Radar Profile

The radar profile shows very high scores in all dimensions, indicating a lecture that is both information-dense and technically rigorous. The high 'niveau_technique' and 'qualite_information' reflect the advanced mathematical content, while the strong 'fiabilite_globale' underscores the reliability of the source.

Reliability 9/10