Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Analysis of Boolean Functions at CMU - Constraint Satisfaction Problems

Ryan O'Donnell via YouTube

Start learning Write review
DataCamp Ad

PowerBI Data Analyst - Create visualizations and dashboards from scratch

Learn More → Corporate Finance Institute Ad

Build the Finance Skills That Lead to Promotions, Not Just Certificates

Learn More →

Overview

Google, IBM & Meta Certificates – 40% Off
One Coursera Plus subscription covers most Professional Certificates on Coursera.
Unlock All Certificates
This graduate-level lecture introduces constraint satisfaction problems through domains, predicates, and optimization formulations. It connects CSP approximation algorithms with NP-hardness, the PCP theorem, dictatorship tests, and hardness-of-approximation results.

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

Reviews

Start your review of Analysis of Boolean Functions at CMU - Constraint Satisfaction Problems

Start learning

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.