TOP
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
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 25211

The Constraint Satisfaction Problem: Complexity and Approximability

( 18. May – 23. May, 2025 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/25211

Organisatoren

Kontakt

Dagstuhl Reports

As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.

  • Upload (Use personal credentials as created in DOOR to log in)

Dagstuhl Seminar Wiki

Gemeinsame Dokumente

Programm

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, 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.

Copyright Manuel Bodirsky, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný

Teilnehmer

Please log in to DOOR to see more details.

  • Per Austrin (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
  • Libor Barto (Charles University - Prague, CZ) [dblp]
  • Arash Beikmohammadi (Simon Fraser University - Burnaby, CA)
  • Amey Bhangale (University of California - Riverside, US)
  • Manuel Bodirsky (TU Dresden, DE) [dblp]
  • Zarathustra Brady (Setauket, US)
  • Johanna Brunar (TU Wien, AT)
  • Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
  • Silvia Butti (University of Oxford, GB)
  • Karthik C. S. (Rutgers University - New Brunswick, US) [dblp]
  • Siu On Chan (Hong Kong, HK) [dblp]
  • Victor Dalmau (UPF - Barcelona, ES) [dblp]
  • Anuj Dawar (University of Cambridge, GB) [dblp]
  • Dmitry Feichtner-Kozlov (Universität Bremen, DE) [dblp]
  • Florian Frick (Carnegie Mellon University - Pittsburgh, US)
  • Venkatesan Guruswami (University of California - Berkeley, US) [dblp]
  • Santiago Guzmán Pro (TU Dresden, DE)
  • Maximilian Hadek (Charles University - Prague, CZ)
  • Prahladh Harsha (TIFR - Mumbai, IN) [dblp]
  • Johan Hastad (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
  • Peter Jonsson (Linköping University, SE) [dblp]
  • Eun Jung Kim (KAIST - Daejeon, KR & CNRS - Paris, FR) [dblp]
  • Pravesh K. Kothari (Princeton University, US)
  • Marcin Kozik (Jagiellonian University - Kraków, PL) [dblp]
  • Andrei Krokhin (Durham University, GB) [dblp]
  • Euiwoong Lee (University of Michigan - Ann Arbor, US) [dblp]
  • Konstantin Makarychev (Northwestern University - Evanston, US) [dblp]
  • Yury Makarychev (TTIC - Chicago, US) [dblp]
  • Barnaby Martin (Durham University, GB) [dblp]
  • Dániel Marx (CISPA - Saarbrücken, DE) [dblp]
  • Antoine Mottet (TU Hamburg, DE) [dblp]
  • Tomáš Nagy (Jagiellonian University - Kraków, PL)
  • Tamio-Vesa Nakajima (University of Oxford, GB)
  • Jakub Opršal (University of Birmingham, GB) [dblp]
  • George Osipov (Linköping University, SE)
  • Marcin Pilipczuk (University of Warsaw, PL) [dblp]
  • Michael Pinsker (TU Wien, AT) [dblp]
  • Aaron Potechin (University of Chicago, US) [dblp]
  • Xuandi Ren (University of California - Berkeley, US)
  • Jakub Rydval (TU Wien, AT)
  • Žaneta Semanišinová (TU Dresden, DE)
  • Santhoshini Velusamy (TTIC - Chicago, US)
  • Uli Wagner (IST Austria - Klosterneuburg, AT) [dblp]
  • Magnus Wahlström (Royal Holloway, University of London, GB) [dblp]
  • Michal Wrona (Jagiellonian University - Kraków, PL)
  • Dmitriy Zhuk (Charles University - Prague, CZ) [dblp]
  • Stanislav Živný (University of Oxford, 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 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)

Klassifikation
  • Computational Complexity
  • Data Structures and Algorithms

Schlagworte
  • constraint satisfaction problem
  • computational complexity
  • hardness of approximation
  • semidefinite programming
  • parameterized complexity