Friday, November 14, 20142:00 pmCUNY Logic WorkshopGC 6417

Algebraic and model-theoretic methods in constraint satisfaction

Michael Pinsker

Université Diderot – Paris 7

The Constraint Satisfaction Problem (CSP) of a first-order structure S in a finite relational language is the problem of deciding whether a given conjunction of atomic formulas in that language is satisfiable in S. Many classical computational problems can be modeled this way. The study of the complexity of CSPs involves an interesting combination of techniques from universal algebra, Ramsey theory, and model theory. I will present an overview over these techniques as well as some wild conjectures.