Analysis of Boolean Functions at CMU - Constraint Satisfaction Problems

Offered By: Ryan O'Donnell via YouTube

Course Description

Overview

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.

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

Automata Theory
Stanford University via edX Intro to Theoretical Computer Science
Udacity Computing: Art, Magic, Science
ETH Zurich via edX 理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX Quantitative Formal Modeling and Worst-Case Performance Analysis
EIT Digital via Coursera