Skip to main content

Constraint Satisfaction Problems

Computational problems from many different application areas can be seen as constraint satisfaction problems. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or interpreting a visual image, can all be seen in this way. In any constraint satisfaction problem there is a collection of variables which all have to be assigned values, subject to specified constraints. An equivalent way of defining constraint satisfaction problems is via homomorphisms between relational structures. Our goal is to understand the computational complexity of constraint satisfaction problems.

Head of Activity


Emeritus Faculty


Lorenzo Ciardo
(Junior Research Fellow at Kellogg College)

Past Members

Miriam Backens
Clement Carbonnel
Conrad Drescher
Peter Fulla
Matthias Lanzinger
Balázs Mezei
Jakub Opršal
Justyna Petke
David Richerby
Miguel Romero
András Salamon
Shuai Shao
Evgenij Thorstensen
Caterina Viola
Marcin Wrochna
Lei Xu

Selected Publications

View All