Completed
The Dichotomy Conjecture Theorem
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
The Complexity of Satisfiable CSPs
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Constraint Satisfaction Problems
- 3 The Dichotomy Conjecture Theorem
- 4 Polymorphisms: example for 2SAI
- 5 Approximation Dichotomy Conjecture
- 6 Raghavendra's Theorem
- 7 Our guess: Abelian Structure
- 8 Components
- 9 Dictatorship tests
- 10 A related analytical question
- 11 Techniques
- 12 Future Directions: Embeddings Philosophy
