YoVDO

Constraint Satisfaction Problems - Lecture 20b of CS Theory Toolkit

Offered By: Ryan O'Donnell via YouTube

Tags

Constraint Satisfaction Problems Courses Algorithms Courses Theoretical Computer Science Courses

Course Description

Overview

Explore Constraint Satisfaction Problems (CSPs) in this graduate-level lecture from Carnegie Mellon University's "CS Theory Toolkit" course. Delve into formal definitions, the Dichotomy Conjecture (now Theorem), and its significance in theoretical computer science. Learn about CSP examples, algorithms, and satisfiability. Gain insights from additional resources on CSP approximability and polymorphisms. Taught by Ryan O'Donnell, this 32-minute video offers a comprehensive look at fundamental concepts essential for research in theoretical computer science.

Syllabus

Introduction
Constraint Satisfaction Problems
Formal Definition
Examples
CSPs
Algorithms
Satisfiability


Taught by

Ryan O'Donnell

Related Courses

Information Theory
The Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera