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/hypergraph colorability, and systems of equations. The CSP framework originated around 40 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 offering a good balance between generality and 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 counting assignments or involve 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 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 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 study is the variety of different branches of mathematics (including universal algebra and logic, combinatorics and graph theory, probability theory and mathematical programming) that are used to achieve deep insights into CSP, and this Dagstuhl Seminar aims to contribute towards further synergy in the area.

After about 15 years of intense research activity and hugely impressive progress, the culmination of the algebraic-approach to fixed-template CSPs was the resolution of the Feder-Vardi conjecture independently by Bulatov and Zhuk in 2017. While some fundamental questions (such as a fine-grained understanding of tractable CSPs) remain open, new research directions on generalizations of CSPs started emerging. The fixed-template promise CSP (PCSP) is among the most promising new directions of research motivated by better understanding computational hardness or tractability. PCSPs are a vast generalization of CSPs where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. A prime and well-known example is the approximate graph coloring problem: distinguish k-colorable graphs from graphs that are not even ℓ-colorable, for some fixed k<ℓ. The main topic of this seminar is PCSPs, a highly ambitious research direction with intriguing connections to both old open problems (such as the approximate graph coloring problem) and new research directions (such as generalizations of submodularity, a key concept in optimization).

Concluding remarks and future plans. 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 a multitude of impressive results reported during the seminar and 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 another seminar focusing 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.

Description of the Topics of the Seminar

With the resolution of the Feder-Vardi conjecture on finite-domain CSPs by Bulatov and Zhuk in 2017, the field has moved on to more generalizations of finite-domain decision CSPs. One of the main emerging areas is that of Promise CSPs (PCSPs), which are a huge generalization of CSPs.

Promise CSPs

The study of PCSPs is about approximability of perfectly satisfiable instances. This exciting area been the main theme of this workshop, with about half of the talks on PCSPs.

The workshop started with a 2-hour tutorial on the basics of PCSPs.

• In the first part, Opršal talked about basic tools used in the complexity analysis of PCSPs, namely minions and free structures.
• In the second part, Opršal talked about an application of topology in the study of complexity of graph colorings.

There were three topologists attending the seminar and one of them gave a talk.

• Kozlov gave a talk on uses of topology in theoretical computer science and homomorphism questions in particular.

There were 9 contributed talks on recent results on PCSPs.

• Barto talked about his work on "baby PCP", which is a combinatorial variant of a (weaker version of) the PCP theorem.
• Brakensiek gave two talks: one on minions related to SDP relaxations for PCSPs, and one on very recent results on robust solvability of certain PCSPs.
• Butti gave a talk about Sherali-Adams relaxations for valued PCSPs.
• Ciardo gave a talk about Sherali-Adams relaxations for PCSPs, and more generally about studying hierarchies of convex relaxations via tensorisation.
• Dalmau gave a talk about his work on a condition that PCSPs solvable by local consistency algorithms have to satisfy.
• Kompatscher gave an overview of existing results on finite tractability of PCSPs.
• Mottet gave a talk about his very recent work on first-order definable PCSPs and a relationship to PCSPs solved by local consistency algorithms.
• Nakajima gave a talk on the complexity of linearly-ordered colorings.

Approximability of CSPs

The second main theme of the seminar was recent progress in the area of approximability of CSPs. This part of the programme started with a 2-hour tutorial:

• Tulsiani gave a tutorial on how to approximate CSPs via the Sum of Squares hierarchy of SDP relaxations, including related work on high-dimensional expanders.

Three participants gave talks on approximability of CSPs.

• Bhangale gave a talk on approximability of solvable linear equations over non-Abelian groups.
• Kothari presented a refutation algorithm for unsatisfiable instances of SAT and CSP.
• Potechin talked about an algorithm for Max NAE-SAT with clauses of lengths 3 and 5.

Infinite-domain CSPs

The area of infinite-domain CSPs has seen some exciting progress in last few years with new techniques being developed.

• Bodirsky talked about methods for transferring complexity classification result between different classes of infinite-domain CSPs.
• Nagy talked about the complexity of CSPs over random hypergraphs.
• Pinsker gave an overview of recent developments around the dichotomy conjecture for infinite-domain CSPs.

Generalisations of CSPs

There are several interesting research directions related to CSPs, including the number of solutions, CSPs with a bound on the number of occurrences for each variable, quantified CSPs, a generalisation to the ideal membership problem, etc. The seminar featured 5 talks on these topics.

• Austrin presented an algorithmic lowerbound for perfect matching on random graphs, a canonical example of an edge CSP.
• Bulatov gave a talk the ideal membership problem.
• Chen presented his results on property testing of homomorphism inadmissibility.
• Kazeminia presented a classification of counting graph homomorphism modulo 2.
• Zhuk presented a complexity classification of quantified CSPs.

Creative Commons BY 4.0

Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný