Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 12451

The Constraint Satisfaction Problem: Complexity and Approximability

( 04. Nov – 09. Nov, 2012 )

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:





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.

  • 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]

Verwandte Seminare
  • 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)

  • data structures / algorithms / complexity

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