License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.8.6.1
URN: urn:nbn:de:0030-drops-100251
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10025/
Go back to Dagstuhl Reports

Grohe, Martin ; Guruswami, Venkatesan ; Zivny, Stanislav
Weitere Beteiligte (Hrsg. etc.): Martin Grohe and Venkatesan Guruswami and Stanislav Zivny

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231)

pdf-format:
dagrep_v008_i006_p001_18231.pdf (12 MB)

Abstract

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, non-trivially approximable,
fixed-parameter tractable, or definable in a weak logic). In the last decade,
research activity in this area has significantly intensified and hugely
impressive progress was made.
The Dagstuhl Seminar 18231 "The Constraint Satisfaction Problem: Complexity and
Approximability" was aimed at bringing together researchers using all the
different techniques in the study of the CSP so that they can share their
insights obtained during the past three years. This report documents the
material presented during the course of the seminar.

BibTeX - Entry

@Article{grohe_et_al:DR:2018:10025,
  author =	{Martin Grohe and Venkatesan Guruswami and Stanislav Zivny},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231)}},
  pages =	{1--18},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{6},
  editor =	{Martin Grohe and Venkatesan Guruswami and Stanislav Zivny},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10025},
  URN =		{urn:nbn:de:0030-drops-100251},
  doi =		{10.4230/DagRep.8.6.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjecture;}
}

Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjecture;
Freie Schlagwörter (englisch): Parameterised complexity; Descriptive complexity; Universal algebra; Logic; Semidefinite programming
Collection: Dagstuhl Reports, Volume 8, Issue 6
Issue Date: 2018
Date of publication: 19.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI