The Complexity of Satisfiable CSPs

The Complexity of Satisfiable CSPs

Centre de recherches mathématiques - CRM via YouTube Direct link

Techniques

11 of 12

11 of 12

Techniques

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. 1 Intro
  2. 2 Constraint Satisfaction Problems
  3. 3 The Dichotomy Conjecture Theorem
  4. 4 Polymorphisms: example for 2SAI
  5. 5 Approximation Dichotomy Conjecture
  6. 6 Raghavendra's Theorem
  7. 7 Our guess: Abelian Structure
  8. 8 Components
  9. 9 Dictatorship tests
  10. 10 A related analytical question
  11. 11 Techniques
  12. 12 Future Directions: Embeddings Philosophy

Never Stop Learning.

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

Someone learning on their laptop while sitting on the floor.