TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 12451

The Constraint Satisfaction Problem: Complexity and Approximability

( Nov 04 – Nov 09, 2012 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/12451

Organizers

Contact


Schedule

Summary

The constraint satisfaction problem, or CSP in short, provides a unifying framework in which it is possible to express, in a natural way, a wide variety of computational problems dealing with mappings and assignments, including satisfiability, graph colorability, and systems of equations. The CSP framework originated 25-30 years ago independently in artificial intelligence, database theory, and graph theory, under three different guises, and it was realised only in the late 1990s that these are in fact different faces of the same fundamental problem. Nowadays, the CSP is extensively used in theoretical computer science, being a mathematical object with very rich structure that provides an excellent laboratory both for classification methods and for algorithmic techniques, while in AI and more applied areas of computer science this framework is widely regarded as a versatile and efficient way of modelling and solving a variety of real-world problems, such as planning and scheduling, software verification and natural language comprehension, to name just a few.

An instance of CSP consists of a set of variables, a set of values for the variables, and a set of constraints that restrict the combinations of values that certain subsets of variables may take. Given such an instance, the possible questions include (a) deciding whether there is an assignment of values to the variables so that every constraint is satisfied, or optimising such assignments in various ways, or (b) finding an assignment satisfying as many constraints as possible. There are many important modifications and extensions of this basic framework, e.g. those that deal with soft or global constraints.

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). It is only natural that CSPs play a role in many high-profile conjectures in complexity theory, exemplified by the Dichotomy Conjecture of Feder and Vardi and the Unique Games Conjecture of Khot.

The recent flurry of activity on the topic of the seminar is witnessed by two previous Dagstuhl seminars, titled "Complexity of constraints" (06401) and "The CSP: complexity and approximability" (09441), that were held in 2006 and 2009, respectively. This seminar was a follow-up to the 2009 seminar. Indeed, the exchange of ideas at the 2009 seminar has led to new ambitious research projects and to establishing regular communications channels, and there is a clear potential of a further systematic interaction that will keep on cross-fertilizing the areas and opening new research directions. The 2012 seminar brought together forty four researchers from different highly advanced areas of constraint satisfaction and involved many specialists who use universal-algebraic, combinatorial, geometric and probabilistic techniques to study CSP-related algorithmic problems.

The seminar included two substantial tutorials: one on the classification of the complexity of constraint languages via methods of logic and universal algebra (given by A. Krokhin from Durham U, UK and R. Willard from Waterloo U, CA), and the other on the approximability of CSP (given by P. Austrin from KTH Stockholm, SE). Other participants presented, in 28 further talks, their recent results on a number of important questions concerning the topic of the seminar.

The seminar was well received as witnessed by the high rate of accepted invitations and the great degree of involvement by the participants. Because of the multitude of impressive results reported during the seminar and the active discussions between researchers with different expertise areas, the organisers regard this seminar as a great success. With steadily increasing interactions between such researchers, we foresee a new seminar focussing on the interplay between different approaches to studying the complexity and approximability of the CSP. Finally, the organisers wish to express their gratitude to the Scientific Directors of the Dagstuhl Centre for their support of the seminar.


Participants
  • Albert Atserias (UPC - Barcelona, ES) [dblp]
  • Per Austrin (KTH Royal Institute of Technology, SE) [dblp]
  • Libor Barto (Charles University - Prague, CZ) [dblp]
  • Manuel Bodirsky (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
  • Catarina Alexandra Carvalho (University of Hertfordshire, GB) [dblp]
  • Hubie Chen (Universidad del País Vasco - Donostia, ES) [dblp]
  • David Cohen (Royal Holloway University of London, GB) [dblp]
  • Victor Dalmau (UPF - Barcelona, ES) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Leslie Ann Goldberg (University of Liverpool, GB) [dblp]
  • Martin Grohe (RWTH Aachen, DE) [dblp]
  • Venkatesan Guruswami (Carnegie Mellon University, US) [dblp]
  • Gregory Z. Gutin (Royal Holloway University of London, GB) [dblp]
  • Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
  • Sangxia Huang (KTH Royal Institute of Technology, SE) [dblp]
  • Anna Huber (Durham University, GB) [dblp]
  • Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
  • Peter Jonsson (Linköping University, SE) [dblp]
  • Vladimir Kolmogorov (IST Austria - Klosterneuburg, AT) [dblp]
  • Marcin Kozik (Jagiellonian University - Kraków, PL) [dblp]
  • Stefan Kratsch (TU Berlin, DE) [dblp]
  • Andrei Krokhin (Durham University, GB) [dblp]
  • Benoit Larose (Champlain Regional College - St. Lambert, CA) [dblp]
  • Pinyan Lu (Microsoft Research Asia, CN) [dblp]
  • Konstantin Makarychev (Microsoft Corporation - Redmond, US) [dblp]
  • Yury Makarychev (TTIC - Chicago, US) [dblp]
  • Petar Markovic (University of Novi Sad, RS)
  • Barnaby Martin (Middlesex University - London, GB) [dblp]
  • Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Ralph McKenzie (Vanderbilt University - Nashville, US)
  • Michael Pinsker (University Paris-Diderot, FR) [dblp]
  • Prasad Raghavendra (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Francesco Scarcello (University of Calabria, IT) [dblp]
  • Ola Svensson (EPFL - Lausanne, CH) [dblp]
  • Stefan Szeider (TU Wien, AT) [dblp]
  • Suguru Tamaki (Kyoto University, JP) [dblp]
  • Johan Thapper (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Matt Valeriote (McMaster University - Hamilton, CA) [dblp]
  • Moshe Y. Vardi (Rice University - Houston, US) [dblp]
  • Magnus Wahlström (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Ross Willard (University of Waterloo, CA) [dblp]
  • Yuichi Yoshida (National Institute of Informatics - Tokyo, JP) [dblp]
  • Stanislav Živný (University of Warwick - Coventry, GB) [dblp]

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 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)
  • Dagstuhl Seminar 25211: The Constraint Satisfaction Problem: Complexity and Approximability (2025-05-18 - 2025-05-23) (Details)

Classification
  • data structures / algorithms / complexity

Keywords
  • constraint satisfaction problem (CSP)
  • computational complexity
  • CSP dichotomy conjecture
  • hardness of approximation
  • unique games conjecture
  • descriptive complexity
  • universal algebra
  • logic
  • decomposition methods