Introduction to the complexity of CSPs (NMAG563), winter semester 2020/2021
Date | Description | Material |
09/10 | Introductory lecture | Survey (sections 1 and 2) Video recording Notes |
16/10 | Polynomial-time algorithms for boolean CSPs | Exercise sheet 1 (Problems 0 to 2) |
23/10 | More algorithms, and reductions between CSPs | Exercise sheet 1 (Problems 3 to 5) Exercise sheet 2 (Problems 1 to 3) Notes |
30/10 | Cores, reductions | Exercise sheet 2 (Problems 4 to 7) |
06/11 | Polymorphisms | Exercise sheet 3 (Problems 1 to 6) |
13/11 | Polymorphisms | Exercise sheet 3 (Problems 7 to 10) |
20/11 | Clones over the two-element set | Exercise sheet 4 |
27/11 | Schaefer's dichotomy theorem | Exercise sheet 5 |
04/12 | Minimality | Exercise sheet 6 (Problems 1 to 3) |
11/12 | Minimality | Exercise sheet 6 (Problems 4 to 8) |
18/12 | Maltsev constraints | Exercise sheet 7 |
15/01 | The Hell-Nešetřil Theorem | Exercise sheet 8 Notes |