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.