Research
A current research topic at the chair is the computational complexity of Constraint Satisfaction Problems. The questions raised in this context are closely linked to central questions in universal algebra and model theory.
© M. Bodirsky
Current research topics
- Model theory
- Finite Model Theory
- Universal Algebra
- Ramsey theory, infinite permutation groups, homogeneous structures
- Constraint satisfaction problems: algorithms and complexity
One of our current research topics is the computational complexity of constraint satisfaction problems. CSPs are computational problems that appear in many areas of theoretical computer science, such as temporal and spatial reasoning, optimisation, veri cation, computational linguistics, scheduling. Efficient algorithms or hardness results for CSPs are often of central interest in these areas. It is highly desirable to obtain complete complexity classifications for large classes of CSPs. Over the past years, a fruitful connection between complexity classification for CSPs and areas of mathematics such as universal algebra and model theory has emerged. This has led to deep results about the complexity of CSPs in one direction, and in the other direction to stimulating questions in universal algebra, model theory, and Ramsey theory, motivated by CSPs, that are central to these fields.
Here is a postprint of my book with the title "Complexity of Infinite-Domain Constraint Satisfaction" which appeared in the LNL Series of Cambridge University Press.