Antoine Mottet

Introduction to the complexity of CSPs (NMAG563)

Thursdays at 9.00am, in the seminar room of the Department of Algebra.
DateDescriptionMaterial
10/10Introductory lectureSurvey (sections 1 and 2)
17/10Polynomial-time algorithms for boolean CSPsExercise sheet 1
24/10, 31/10, 07/11Reductions between CSPs, coresExercise sheet 2
14/11, 21/11PolymorphismsExercise sheet 3
28/11, 5/12, 12/12Schaefer's dichotomy theoremExercise sheet 4
19/12, 09/01Schaefer's dichotomy theoremExercise sheet 5