Constraint Satisfaction: Algorithms and Complexity

Instructors:	Manuel Bodirsky and Miki Hermann
Dates:	13/09/2011 until 28/02/2012. No course at 31/01/2012!
Time:	Tuesday 14.15 am until 15.45 am
Classroom:	Room 1E01 (backup 0D7) at Paris 7, Chevaleret.

This is the course website for the first part of the MPRI course 2-31-1 Constraint Satisfaction: Algorithms and Complexity.

The topic of this part of the course are graph homomorphism problems and constraint satisfaction problems with infinite domains, with a particular focus on constraint satisfaction problems that can be solved in polynomial time.

The web-site for the first part of the course can be found here.

Slides

Some of the topics of the course are illustrated by slides. The course slides will be available after they have been presented in the lecture. Important: these slides cover only a fraction of the material that is presented in the lecture!

Script(s)

The course script for the present course is available here; the text is still subject to modifications. Comments, bugreports, and questions are welcome.

My habilitation is about complexity classification in infinite domain constraint satisfaction, and closely related to the course.

Work-sheets

Exam

Takes place at the 6th of March, at the usual place and time of the lecture.

Stages

The students of the MPRI are highly welcome to do their MPRI research project on topics related to this course. Here are descriptions of research projects that can be pursued. Other projects are possible.

Set constraints: algorithms and complexity. For computer scientists. A detailed description can be found here.
The expressive power of equality constraint languages. For mathematicians. A detailed description can be found here.

Formalities about doing your stage at the MPRI can be found here.