Antoine Mottet

Introduction to the complexity of CSPs (NMAG563), winter semester 2020/2021

DateDescriptionMaterial
09/10Introductory lectureSurvey (sections 1 and 2)
Video recording
Notes
16/10Polynomial-time algorithms for boolean CSPsExercise sheet 1 (Problems 0 to 2)
23/10More algorithms, and reductions between CSPsExercise sheet 1 (Problems 3 to 5)
Exercise sheet 2 (Problems 1 to 3)
Notes
30/10Cores, reductionsExercise sheet 2 (Problems 4 to 7)
06/11PolymorphismsExercise sheet 3 (Problems 1 to 6)
13/11PolymorphismsExercise sheet 3 (Problems 7 to 10)
20/11Clones over the two-element setExercise sheet 4
27/11Schaefer's dichotomy theoremExercise sheet 5
04/12MinimalityExercise sheet 6 (Problems 1 to 3)
11/12MinimalityExercise sheet 6 (Problems 4 to 8)
18/12Maltsev constraintsExercise sheet 7
15/01The Hell-Nešetřil TheoremExercise sheet 8
Notes