03. – 08. Juni 2018, Dagstuhl-Seminar 18231

The Constraint Satisfaction Problem: Complexity and Approximability


Martin Grohe (RWTH Aachen, DE)
Venkatesan Guruswami (Carnegie Mellon University – Pittsburgh, US)
Dániel Marx (Hungarian Academy of Sciences – Budapest, HU)
Stanislav Živný (University of Oxford, GB)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]


The main aim of this Dagstuhl Seminar is to bring together leading researchers from all areas of activity in the theory of computation who use the constraint satisfaction paradigm, so that they can communicate state-of-the-art advances, share deep insights, and embark on a systematic interaction that will further develop the synergy between the different areas, generate new research avenues, and lead to fruitful attacks on the open problems in this area.

Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g. polynomial-time solvable or non-trivially approximable, fixed-parameter tractable or definable in a weak logic). One of the most striking features of this research direction is the variety of different branches of mathematics (including algebra and logic, combinatorics and graph theory, probability theory and mathematical programming) that are used to achieve deep insights in the study of the CSP, and this seminar will contribute towards further synergy in the area. In the last decade, research activity in this area has significantly intensified and hugely impressive progress was made, but some of the central questions remain open to date.

The main topics addressed during the seminar will include complexity dichotomies for CSP and related problems, approximability of CSPs, parameterized complexity of CSPs, and logical approaches to CSPs. The participants will also explore the interactions between these topics.

  Creative Commons BY 3.0 DE
  Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný

Dagstuhl-Seminar Series


  • Data Structures / Algorithms / Complexity


  • Constraint satisfaction problem (CSP)
  • Computational complexity
  • CSP dichotomy conjecture
  • Hardness of approximation
  • Unique games conjecture
  • Parameterized complexity
  • Descriptive complexity
  • Universal algebra
  • Logic
  • Semidefinite programming


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.