Analysis of Boolean Functions at CMU - Lecture 16: Håstad's hardness theorems

Analysis of Boolean Functions at CMU - Lecture 16: Håstad's hardness theorems

by Ryan O'Donnell

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

Keywords

stable influencedictatorship testno notable coordinates3XOR3SAThardness of approximationUnique Games ConjecturePCP theoremFourier analysisnoise stability

Summary

This lecture, part of a graduate course on Analysis of Boolean Functions at CMU, focuses on Håstad’s hardness theorems for approximating constraint satisfaction problems (CSPs). The instructor introduces the concept of ‘stable influence’ of a coordinate, which attenuates contributions from large Fourier coefficients. He proves that for any function with variance at most 1, the number of coordinates with large stable influence is bounded. This leads to the definition of ’no notable coordinates’ functions, which are far from dictators. The lecture then presents a relaxed dictatorship test, the ‘dictator vs. no notables test’, which accepts dictators with high probability and rejects functions with no notable coordinates with low probability. The instructor states a theorem that such a test implies hardness of approximation for the associated CSP, assuming the Unique Games Conjecture. He then outlines the design of tests for 3XOR and 3SAT, which are based on the BLR linearity test, and mentions that the analysis will be covered in subsequent lectures. The lecture concludes by noting that these tests yield hardness results that are slightly weaker than Håstad’s original NP-hardness results.

181 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a rigorous and insightful exposition of the connection between dictatorship testing and hardness of approximation. The introduction of stable influence is well-motivated and its properties are clearly demonstrated. The argumentation is solid, with formal definitions, theorems, and proofs. The instructor carefully explains the intuition behind each concept, making the material accessible despite its technical depth. The presentation is well-structured, building from basic definitions to the main theorem and its applications.

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 sources in the field. The content is mathematically rigorous, with precise definitions and proofs. The title accurately reflects the content, which focuses on Håstad’s hardness theorems. The lecture is part of a well-established graduate course, ensuring high quality and reliability.

148 words

Title / Content Match

The title accurately reflects the content, which focuses on Håstad's hardness theorems and their connection to dictatorship testing and Fourier analysis.

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, with formal definitions, theorems, and proofs. The presentation is clear and well-structured, suitable for a graduate-level audience.

Key Moments

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

Cited Sources

  • Analysis of Boolean Functions (textbook) — The course textbook, which contains the material presented in the lecture.
  • Course website — The course website for the lecture series.
  • Author's homepage — The instructor's homepage, providing additional resources.
  • Analysis of Boolean Functions website — The website for the textbook and related materials.
  • Panopto — The video recording platform used for the lecture.

Concurring Sources

  • Analysis of Boolean Functions (textbook) — The textbook provides a comprehensive treatment of the topics covered in the lecture, including stable influence and dictatorship testing.
  • Course website — The course website contains lecture notes and additional materials that align with the content of this lecture.

Contribution & Novelties

This lecture provides a clear and detailed exposition of the connection between dictatorship testing and hardness of approximation, specifically focusing on Håstad’s theorems. The introduction of stable influence as a tool to identify notable coordinates is a key contribution, as it allows for a relaxed dictatorship test that is easier to analyze. The lecture also highlights the role of the Unique Games Conjecture in obtaining hardness results from such tests.

Pour aller plus loin :

  • Håstad’s 3XOR hardness — This theorem is a central result in hardness of approximation, showing that it is NP-hard to approximate 3XOR beyond a certain threshold.
  • Unique Games Conjecture — This conjecture, if true, would imply optimal hardness results for many CSPs, including those discussed in the lecture.
  • PCP theorem — The PCP theorem is a foundational result in computational complexity that underpins many hardness of approximation results, including those based on dictatorship testing.

149 words

Radar Profile

The radar profile shows high scores in all dimensions, indicating a lecture that is both information-dense and technically rigorous. The high level of technical detail is balanced by clear explanations, making it suitable for an advanced audience. The overall quality is excellent, with strong scores in information quality and reliability.

Reliability 9/10