Analysis of Boolean Functions at CMU - Lecture 9: Majority, LTFs, and the CLT

Analysis of Boolean Functions at CMU - Lecture 9: Majority, LTFs, and the CLT

by Ryan O'Donnell

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

Keywords

Boolean functionsFourier analysislinear threshold functionscentral limit theoremmajority

Summary

This is the ninth lecture of a graduate course on Analysis of Boolean Functions taught by Ryan O’Donnell at CMU. The lecture focuses on linear threshold functions (LTFs) and majority, and how the central limit theorem (CLT) can be used to analyze their properties. The instructor begins by defining LTFs as sign of a linear form, and discusses their geometric interpretation as half-spaces. He then proves Chow’s theorem, which states that an LTF is uniquely determined by its degree-0 and degree-1 Fourier coefficients. Next, he proves a theorem by Gotzman and Linial showing that the weight of an LTF on degree-0 and degree-1 coefficients is at least 1/2. The lecture then introduces the central limit theorem and its quantitative version, the Berry-Esseen theorem, which provides error bounds. As an application, the instructor uses the CLT to compute the total influence of the majority function, showing it is asymptotically sqrt(2/pi) * sqrt(n). The lecture concludes with a discussion of the conjecture that the weight on degree-0 and degree-1 coefficients is at least 2/pi for any LTF, and mentions recent progress. The presentation is rigorous, with proofs and references to homework problems.

190 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a solid introduction to linear threshold functions and their analysis via Fourier analysis and the central limit theorem. The proofs are well-structured and build on previously established results. The use of the CLT to compute the influence of majority is elegant and illustrates the power of probabilistic methods. The argumentation is clear and rigorous, with appropriate caveats about the limitations of the CLT and the need for error bounds.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is based on the instructor’s own textbook ‘Analysis of Boolean Functions’ and is part of a well-known graduate course. The sources cited are relevant and include the course website and the textbook. The title accurately reflects the content. The presentation is scientifically rigorous, with careful proofs and references to known theorems. No comments were provided for analysis.

146 words

Title / Content Match

The title accurately reflects the content: the lecture focuses on majority, linear threshold functions, and the central limit theorem.

Quality & Reliability

9/10

Lecture by a recognized expert in theoretical computer science, based on a well-established textbook and course. The content is rigorous, with proofs and references to known theorems (Chow's theorem, Berry-Esseen). The presentation is clear and technically accurate.

Key Moments

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

Cited Sources

  • Analysis of Boolean Functions (textbook) — The free textbook for the course, which contains the material presented in the lecture.
  • Course website — The official website for the course, providing lecture notes and other resources.
  • Ryan O'Donnell's homepage — The instructor's academic homepage.
  • Analysis of Boolean Functions website — Website dedicated to the topic, with additional resources.
  • Panopto — The video recording platform used to film the lecture.

Concurring Sources

  • Analysis of Boolean Functions (textbook) — The textbook contains the same theorems and proofs presented in the lecture.

Contribution & Novelties

This lecture provides a rigorous introduction to linear threshold functions and demonstrates the power of the central limit theorem in analyzing their properties. The proof of Chow’s theorem and the weight bound are presented clearly. The use of the CLT to compute the influence of majority is a nice illustration of probabilistic methods in Boolean function analysis.

Pour aller plus loin :

  • Central limit theorem — The fundamental theorem in probability that underlies the lecture’s approach.
  • Berry-Esseen theorem — Provides quantitative error bounds for the CLT, as discussed in the lecture.
  • Linear threshold function — The class of functions studied in the lecture.
  • Fourier analysis on Boolean functions — The mathematical framework used throughout the course.

116 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a lecture that is both information-dense and technically rigorous. The balance between quantity and quality of information is excellent, and the technical level is appropriate for a graduate course.

Reliability 9/10