Explore constraint satisfaction problems in this 75-minute graduate-level lecture from Carnegie Mellon University's course on Analysis of Boolean Functions. Delve into topics such as generic CSP, Max3sat, Max3coloring, CSP linearity tests, approximation algorithms, and the PCP theorem. Gain insights from Professor Ryan O'Donnell's expertise and benefit from references to the free textbook and course website for further study.
Analysis of Boolean Functions at CMU - Constraint Satisfaction Problems
Overview
Syllabus
Introduction
Generic CSP
Max3sat
Max3coloring
Assignments
CSP
Linearity test
Approximation algorithms
Approximating Max III Lin
Textbook statements
PCP theorem
Polytime approximation
Host theorems
Taught by
Ryan O'Donnell
Related Courses
-
Constraint Satisfaction Problems - Lecture 20b of CS Theory Toolkit
-
Crash Course on Probabilistically Checkable Proofs - Introduction
-
Analysis of Boolean Functions at CMU - Additive Combinatorics
-
The Complexity of Satisfiable CSPs
-
Analysis of Boolean Functions - Restrictions and the Goldreich-Levin Theorem
-
Fourier Analysis of Boolean Functions - Lecture 8a of CS Theory Toolkit
