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

Visit website for this news | Export event in iCalendar format

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


About LSV

Agenda

Export agenda in iCalendar format | Past seminars

Tue, Feb 19

Past seminars