Analysis of Boolean Functions at CMU - Lecture 6: Restrictions and the Goldreich--Levin Theorem

Analysis of Boolean Functions at CMU - Lecture 6: Restrictions and the Goldreich--Levin Theorem

by Ryan O'Donnell

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

Keywords

Fourier coefficientsrestrictionsGoldreich-Levinlearning theorypseudorandom generators

Summary

This lecture from a graduate course on Analysis of Boolean Functions covers two main topics: restrictions and the Goldreich-Levin theorem. The first part introduces the concept of restrictions, where some input bits are fixed, and derives a formula for the Fourier coefficients of the restricted function in terms of the original function’s Fourier coefficients. The lecture then discusses how these coefficients vary as a function of the fixed bits, leading to key identities involving expectations and Parseval’s theorem. The second part presents the Goldreich-Levin theorem, which provides an algorithm to find all large Fourier coefficients of a Boolean function given query access. The theorem is motivated by cryptographic applications, specifically constructing pseudorandom generators from one-way permutations. The lecture concludes by outlining the theorem’s statement and its connection to learning theory.

130 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a rigorous and detailed exposition of restrictions and the Goldreich-Levin theorem. The argumentation is solid, with careful derivations and clear explanations of each step. The value lies in the deep insights into Fourier analysis of Boolean functions and its applications to learning theory and cryptography. The lecturer builds intuition through examples and gradually increases complexity, making the material accessible while maintaining technical precision.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is based on the lecturer’s own textbook ‘Analysis of Boolean Functions’, which is a standard reference in the field. The sources cited are authoritative and directly relevant. The title accurately describes the content, and the lecture maintains a high level of scientific rigor throughout. No comments were provided, so no analysis of public reception is included.

139 words

Title / Content Match

The title accurately reflects the content: the lecture covers restrictions and the Goldreich-Levin theorem.

Quality & Reliability

9/10

Lecture by a recognized expert in the field, based on a well-established textbook, with rigorous mathematical derivations and clear explanations. The content is technical and precise, with no apparent errors or unsupported claims.

Key Moments

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

Cited Sources

Concurring Sources

Contribution & Novelties

The lecture provides a clear and rigorous exposition of restrictions and the Goldreich-Levin theorem, with a focus on the underlying Fourier analytic techniques. The original contribution lies in the pedagogical approach and the emphasis on the connection between learning theory and cryptography.

Pour aller plus loin :

  • Goldreich-Levin theorem — Overview and historical context.
  • Fourier analysis on Boolean functions — General background.
  • Pseudorandom generator — Definition and cryptographic significance.

69 words

Radar Profile

The radar profile shows very high scores across all dimensions, indicating a technically deep, well-sourced, and highly reliable lecture. The balance between quantity and quality of information is excellent, with a strong emphasis on formal rigor.

Reliability 9/10