http://www.dagstuhl.de/15301

July 19 – 24 , 2015, Dagstuhl Seminar 15301

The Constraint Satisfaction Problem: Complexity and Approximability

Organizers

Andrei A. Bulatov (Simon Fraser University – Burnaby, CA)
Venkatesan Guruswami (Carnegie Mellon University – Pittsburgh, US)
Andrei Krokhin (Durham University, GB)
Dániel Marx (Hungarian Academy of Sciences – Budapest, HU)

For support, please contact

Dagmar Glaser for administrative matters

Marc Herbstritt for scientific matters

Documents

Dagstuhl Seminar Wiki

(Use seminar number and access code to log in)

Motivation

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 7-8 years, 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 counting CSPs. The participants will also explore the interactions between these topics.

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity

Keywords

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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, 1st floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.