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.
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.