Analysis of Boolean Functions at CMU - Lecture 2: Probability densities and BLR linearity testing

Analysis of Boolean Functions at CMU - Lecture 2: Probability densities and BLR linearity testing

by Ryan O'Donnell

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

Keywords

Boolean functionsFourier coefficientsprobability densityconvolutionBLR linearity test

Summary

This is the second lecture in a graduate course on Analysis of Boolean Functions, taught by Ryan O’Donnell at Carnegie Mellon University. The lecture begins by reviewing the Fourier expansion of Boolean functions, emphasizing the flexibility in representing bits as ±1 or 0/1. It then introduces probability density functions on the Boolean cube, explaining how they correspond to probability distributions relative to the uniform distribution. The concept of convolution is defined for functions on the Boolean cube, and it is shown that the Fourier transform of a convolution is the pointwise product of the Fourier transforms. The lecture then transitions to the application of linearity testing, introducing the BLR (Blum-Luby-Rubinfeld) linearity test. The instructor discusses two equivalent definitions of linearity for functions over F2, and then considers approximate linearity, posing the question of whether two natural notions of approximate linearity are equivalent. The lecture sets the stage for proving the BLR theorem, which states that if a function is approximately linear in one sense, it is close to a truly linear function. The presentation is rigorous, with detailed proofs and intuitive explanations, suitable for a graduate-level theoretical computer science audience.

190 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a solid foundation in the mathematical tools needed for the analysis of Boolean functions. The value lies in the clear exposition of probability densities and convolution, which are essential for understanding the BLR linearity test. The argumentation is rigorous: definitions are precise, and proofs are given for key results such as the Fourier transform of a convolution. The instructor also motivates the material by connecting it to the application of property testing, making the content relevant and engaging. The reasoning is logical and well-structured, with careful attention to details like the change of variables in the proof of the convolution theorem.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is based on the instructor’s own textbook ‘Analysis of Boolean Functions’ and the course materials, which are authoritative in the field. The sources cited are the course website and the textbook’s website, both of which are reliable. The title accurately reflects the content, as the lecture indeed covers probability densities, convolution, and BLR linearity testing. The presentation is scientifically rigorous, with formal definitions and proofs. The instructor is a recognized expert, and the content aligns with established knowledge in the field. The lecture is well-suited for a graduate-level audience, and the technical level is appropriate for the topic.

219 words

Title / Content Match

The title accurately reflects the content: the lecture covers probability densities, convolution, and BLR linearity testing, as promised.

Quality & Reliability

9/10

Lecture by a recognized expert in the field, based on a well-established textbook and course materials. The content is rigorous and mathematically sound, with clear definitions and proofs. The presentation is formal and precise, suitable for a graduate-level audience.

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 covers the same material in more depth, providing a consistent reference.

Contribution & Novelties

This lecture provides a clear and rigorous introduction to probability densities and convolution on the Boolean cube, and their connection to Fourier analysis. The BLR linearity test is presented as a motivating application, and the lecture sets up the framework for proving the BLR theorem. The original contribution is the pedagogical approach, which emphasizes the interplay between Fourier analysis and property testing.

Pour aller plus loin :

  • Fourier analysis on finite abelian groups — Provides background on characters and Fourier transforms on groups like F2^n.
  • Property testing — Overview of the field of property testing, including linearity testing.
  • BLR linearity test — Detailed description of the BLR test and its analysis.

111 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a lecture that is rich in information, technically deep, and highly reliable. The balance between quantity and quality of information is excellent, and the technical level is appropriate for the target audience.

Reliability 9/10

💬 No comments were provided for analysis.