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 algorithmic problems, including propositional satisfiability, graph colorability, and systems of equations. This framework has been extensively used in theoretical computer science, both as a mathematical object with rich structure that deserves investigation in its own right and as a versatile vehicle for algorithmic techniques. The constraint satisfaction problem was studied in the 1970s by researchers in artificial intelligence working on computer vision. From the 1980s on, it has been studied in database theory under the guise of the conjunctive query containment problem, as well as in combinatorics and finite model theory under the name of the homomorphism problem for graphs and for arbitrary relational structures. Only in the last decade, however, it was realized that all these problems are different faces of the same fundamental problem. Consequently, it is important to analyze and pinpoint the the computational complexity of certain algorithmic tasks related to constraint satisfaction.

Constraint satisfaction has been ubiquitous in computational complexity theory from its early beginnings. For example, as mentioned earlier, propositional satisfiability and graph colorability, two of the very first problems shown to be NP-complete, are particular cases of CSP. Since the constraint satisfaction problem is computationally hard in its full generality, researchers have toiled for the past thirty years to discover tractable cases of CSP and have strived, and continue to strive, to delineate the boundary between tractability and intractability for this problem. During the past two decades, an impressive array of diverse methods from several different mathematical fields, including universal algebra, logic, and graph theory, have been used to analyze both the computational complexity of algorithmic tasks related to the constraint satisfaction problem and the applicability/limitations of algorithmic techniques. Although significant progress has been made on several fronts, some of the central questions remain open to date. The most prominent among them is the Dichotomy Conjecture for the complexity of the decision version of CSP posed by Feder and Vardi in 1993.

The seminar brought together forty researchers from different highly advanced areas of constraint satisfaction and with complementary expertise (logical, algebraic, combinatorial, probabilistic aspects). The list of participants contained both senior and junior researchers and a small number of advanced graduate students.

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 the other on the approximability of CSP (given by V. Guruswami from Carnegie Mellon U, US). The recent breakthroughs on the topic of the seminar were presented by their respective authors in one-hour lectures, as follows:

1. P. Austrin (New York U, US), Approximation Resistance
2. A. Bulatov (Simon Fraser U, CA), Counting CSP
3. M. Kozik (Jagiellonian U, PL), CSPs of Bounded Width
4. D. Marx (Tel Aviv U, IL), Structural Complexity of CSPs: The Role of Treewidth and Its Generalisations
5. P. Raghavendra (U Washington, US), Complexity of Approximating CSPs.

Other participants presented, in 19 further 30-minute talks, their re- cent results on a number of important questions concerning the topic of the seminar.

The seminar was essentially the first meeting of researchers from both the constraint satisfaction community and the complexity of approximation community. The general consensus was that both communities have learned a lot about the goals, methods and techniques of one another, and that there is a potential of a systematic interaction that may cross- fertilize the areas and open new research directions, so it is worthwhile to maintain communication and to arrange further joint meetings.