Dagstuhl Seminar 25211
The Constraint Satisfaction Problem: Complexity and Approximability
( May 18 – May 23, 2025 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25211
Organizers
- Manuel Bodirsky (TU Dresden, DE)
- Venkatesan Guruswami (University of California - Berkeley, US)
- Dániel Marx (CISPA - Saarbrücken, DE)
- Stanislav Živný (University of Oxford, GB)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
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, and most recently topology) 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 20 years, research activity in this area has significantly intensified and hugely impressive progress was made.
The main topics addressed during the seminar will include complexity dichotomies for CSP and related problems, promise CSPs, approximability of CSPs, counting CSPs, and parameterized complexity of CSPs. The participants will also explore the interactions between these topics.
Creative Commons BY 4.0
Manuel Bodirsky, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný
Related Seminars
- Dagstuhl Seminar 06401: Complexity of Constraints (2006-10-01 - 2006-10-06) (Details)
- Dagstuhl Seminar 09441: The Constraint Satisfaction Problem: Complexity and Approximability (2009-10-25 - 2009-10-30) (Details)
- Dagstuhl Seminar 12451: The Constraint Satisfaction Problem: Complexity and Approximability (2012-11-04 - 2012-11-09) (Details)
- Dagstuhl Seminar 15301: The Constraint Satisfaction Problem: Complexity and Approximability (2015-07-19 - 2015-07-24) (Details)
- Dagstuhl Seminar 18231: The Constraint Satisfaction Problem: Complexity and Approximability (2018-06-03 - 2018-06-08) (Details)
- Dagstuhl Seminar 22201: The Constraint Satisfaction Problem: Complexity and Approximability (2022-05-15 - 2022-05-20) (Details)
Classification
- Computational Complexity
- Data Structures and Algorithms
Keywords
- constraint satisfaction problem
- computational complexity
- hardness of approximation
- semidefinite programming
- parameterized complexity
