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