Analysis of Boolean Functions at CMU - Lecture 17: UG-hardness results from dictator tests

Analysis of Boolean Functions at CMU - Lecture 17: UG-hardness results from dictator tests

by John Wright

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

Keywords

Unique GamesDictator TestUG-hardnessCSPReduction

Summary

This lecture, given by John Wright at CMU, focuses on the relationship between the Unique Games Conjecture (UGC) and dictator testing. It begins by defining the Unique Games problem, a constraint satisfaction problem with bijective constraints, and illustrates it with the example of 2-Lin mod Q. The lecture then discusses the known hardness results for approximating Unique Games, noting that the problem is easy when satisfiable, but the UGC posits that it becomes NP-hard to approximate when only 99% satisfiable. The main theorem presented is that any dictator test for a predicate implies UG-hardness for approximating the corresponding CSP, with parameters matching the test. The proof involves a reduction from Unique Games to the CSP, constructing a variable for each vertex and each hypercube point. The lecture also explains how to handle functions that output values in the interval [-1,1] by interpreting them as probability distributions. The reduction ensures that high satisfiability in the Unique Games instance leads to high satisfiability in the CSP, and vice versa, with appropriate parameters. The lecture concludes by outlining the steps of the proof, including the use of regularity and the analysis of the reduction’s performance.

192 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous exposition of a central result in hardness of approximation. The argumentation is solid, building from definitions to a detailed proof sketch. The value lies in connecting abstract concepts (dictator tests) to concrete hardness results, which is a key insight in theoretical computer science. The presentation is well-structured, with careful explanations of each step, making the material accessible to a graduate-level audience.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, based on established research in complexity theory. The sources mentioned include the course website and the lecturer’s personal page, which are appropriate for a lecture. The title accurately reflects the content, and the lecture stays on topic throughout. The presentation is technically accurate, and the proof sketch is consistent with known results in the field.

143 words

Title / Content Match

The title accurately reflects the content: the lecture focuses on deriving UG-hardness results from dictator tests, as part of the Analysis of Boolean Functions course.

Quality & Reliability

8/10

Lecture by a recognized researcher (John Wright) at CMU, part of a graduate course. The content is rigorous, technically detailed, and based on established theoretical computer science concepts. The presentation is clear and well-structured, though it is a lecture without peer review.

Key Moments

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

Cited Sources

  • Analysis of Boolean Functions website — Course website for the Analysis of Boolean Functions course.
  • Free textbook on Analysis of Boolean Functions — Free textbook associated with the course.
  • Course page at CMU — Course page for 15-859S, Fall 2012.
  • John Wright's homepage — Homepage of the guest lecturer.
  • Panopto — Video recording service used for the lecture.

Concurring Sources

  • Analysis of Boolean Functions textbook — The textbook likely covers similar material in more depth.

Contribution & Novelties

This lecture provides a clear and detailed exposition of the connection between dictator tests and UG-hardness, a fundamental technique in hardness of approximation. It offers a step-by-step proof of the reduction, making the material accessible to graduate students. The lecture also clarifies the handling of functions with real-valued outputs, which is a subtle point in the theory.

Pour aller plus loin :

95 words

Radar Profile

The radar profile shows high scores in quantity of information, technical level, and reliability, with slightly lower quality of information due to the lecture format. This indicates a dense, technical, and reliable presentation, suitable for an advanced audience.

Reliability 8/10