Manuel Bodirsky holds a CNRS research position at the École Polytechnique. He wrote his thesis at Humboldt University Berlin. His major research focus is the complexity of constraint satisfaction problems, and he is interested in the mathematical tools from universal algebra, model theory, and combinatorics that can be used to study those problems and their complexity.
Constraint Satisfaction: Finite Model Theory meets Infinite Model Theory
An important topic in finite model theory are logical characterizations of complexity classes. A paradigmatic example of such a characterization is Fagin’s theorem, which describes NP as the model-checking problem for existential second-order logic (ESO).
The question whether a there is a logical characterization for the class P, formalized by Gurevich, is an important open problem in finite model theory. One of the approaches to this problem is to design logics that capture larger and larger fragments of P (typically extensions of least fixed-point logic).
In this talk I present a different approach based on complexity classification for fragments of ESO. This will lead us to infinite-domain constraint satisfaction problems and questions from (infinite) model theory.
