LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Computational Complexity of Constraint Satisfaction Problems
- Date
- Tuesday, February 16 2010 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Manuel Bodirsky (Laboratoire d'Informatique de l'Ecole Polytechnique (LIX))
This talk is an introduction to techniques to determine the computational complexity of constraint satisfaction problems. The central concept here is the notion of a *polymorphism* of a set of constraints. Polymorphisms can be used to translate questions about computational complexity into questions of fundamental importance in universal algebra. I will first give an overview over recent breakthrough results on constraint satisfaction over finite domains based on this translation. Then I give an introduction on how to generalize those techniques from finite to infinite domain constraint satisfaction, and present applications in temporal reasoning.