Analysis of Boolean Functions at CMU - Lecture 4: Noise stability and Arrow's Theorem

Analysis of Boolean Functions at CMU - Lecture 4: Noise stability and Arrow's Theorem

by Ryan O'Donnell

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

Keywords

noise stabilitynoise sensitivityinfluencetotal influenceArrow's theorem

Summary

This is the fourth lecture in a graduate course on Analysis of Boolean Functions at Carnegie Mellon University, taught by Ryan O’Donnell. The lecture begins by revisiting the concepts of influence and total influence, providing a geometric interpretation in terms of the hypercube and deriving a Fourier formula for total influence. This leads to a proof of the Poincaré inequality, which relates variance to total influence and has an isoperimetric interpretation. The main focus of the lecture is then introduced: noise stability and noise sensitivity. These concepts measure how a Boolean function’s output changes when its input is subjected to random noise, motivated by the question of how errors in vote counting affect election outcomes. The lecture computes noise stability for constant, dictator, and parity functions, and discusses the asymptotic behavior for majority function, which converges to a formula involving the arcsine. The lecture concludes with a proof of Arrow’s theorem from social choice, demonstrating that any social welfare function satisfying unanimity and independence of irrelevant alternatives must be a dictatorship. The proof uses the concept of noise stability and the fact that low-influence functions are stable under noise.

189 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a rigorous and self-contained introduction to noise stability and its applications. The argumentation is clear and logically structured, building from definitions to theorems and proofs. The motivation from social choice is effective, making abstract concepts tangible. The proof of Arrow’s theorem is elegant and demonstrates the power of Fourier analysis in social choice theory. The lecture also includes intuitive explanations and examples, enhancing understanding.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is based on the instructor’s own textbook ‘Analysis of Boolean Functions’, which is a standard reference in the field. The mathematical derivations are precise and follow standard practice. The title accurately reflects the content, as the lecture indeed covers noise stability and Arrow’s theorem. The lecture is part of a well-structured course, and the presentation is consistent with the published literature.

145 words

Title / Content Match

The title accurately reflects the content: the lecture covers noise stability and concludes with a proof of Arrow's theorem.

Quality & Reliability

9/10

Lecture by a leading researcher in the field, based on a well-established textbook, with rigorous mathematical derivations and clear definitions. The content is consistent with the published literature on analysis of Boolean functions.

Key Moments

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

Cited Sources

Concurring Sources

  • Analysis of Boolean Functions (book) — The textbook provides the same definitions and theorems.

Contribution & Novelties

This lecture provides a clear and rigorous introduction to noise stability and its application to social choice theory. The proof of Arrow’s theorem using Fourier analysis is a notable contribution, illustrating the power of this approach. The lecture also offers intuitive explanations and examples that aid understanding.

Pour aller plus loin :

80 words

Radar Profile

The radar chart shows high scores across all dimensions, indicating a lecture that is both information-dense and technically rigorous, with excellent reliability and presentation.

Reliability 9/10

💬 No comments were provided for analysis.