April 23, 2014

June 26-30, 2011
Fields Summer School on the Mathematics of Constraint Satisfaction

Titles and Abstracts

Andrei Krokhin (Durham University)
An introduction into mathematics of constraint satisfaction

The constraint satisfaction problem (CSP) provides a general framework in which it is possible to express many problems encountered in mathematics, computer science, and artificial intelligence.

In this course we will introduce the CSP framework, in several equivalent mathematical formulations (including systems of constraints, logical formulas, and homomorphisms between graphs and relational structures), and demonstrate how a wide range of well-known problems can be naturally expressed in it. We will then exhibit a variety of CSP-related mathematical and computational questions that have been studied in the last decade, and explain their relevance. Finally, we will overview the mathematical techniques (other than those presented in depth in three other courses within the summer school) used to tackle these questions, and present a list of open problems.

Jaroslav Nesetril (Charles University)
Colorings and homomorphisms for graphs and finite structures

This course will cover the following topics:
1. Homomorphisms and colorings (sparse incomparability lemma, extension theorem and its relevance to CSP, old and new conjectures)
2. Classes of graphs and structures (4 basic types of classes and their relevance to CSP and model theory)
3. Homomorphism order (the homomorphism order and its properties, limit order)
4. Dualities in many of its forms (characterization of finite dualities, characterization of restricted dualities).

Ross Willard (University of Waterloo)
Universal algebra for constraint satisfaction

Universal algebra is a branch of pure mathematics which studies equationally defined classes of arbitrary algebraic structures. In the 1990s, Jeavons began championing the use of universal algebra to classify tractable constraint satisfaction problems; the methodology he introduced has found increasingly significant application, particularly in attacking the Dichotomy Conjecture of Feder and Vardi.

The first two lectures of this tutorial will give an introduction to the jargon and tools of universal algebra which are most relevant to CSP. After a quick introduction to the basic objects and constructions, I will review the classical correspondence between finite algebras and finite relational structures and then explore the phenomenon of Maltsev conditions (equations satisfied by polymorphisms) restricting the complexity of relational structures. Some fundamental algebraic dichotomies, first discovered using tame congruence theory, will be presented in the important idempotent case.

In the latter two lectures I will sample some of the achievements of the algebraic methodology in CSP. Topics will include the algebraic dichotomy conjecture, the delineation of templates with bounded width, the few subpowers algorithm, and the fine-structure dichotomy conjectures. Throughout, I hope to illustrate arguments that are typical from an algebraic (or at least functional) point of view.

Ryan O'Donnell (CMU), Venkatesan Guruswami (CMU)
Title: The Approximability of Constraint Satisfaction Problems

The optimization problem corresponding to a constraint satisfaction problem (CSP) consists of finding an assignment that satisfies as many constraints of the CSP instance as possible. For most CSPs, including many for which satisfiability can be decided in polynomial time, the associated optimization problem is NP-hard. To cope with this intractability, the approximate solvability of CSPs by polynomial time algorithms and limits on the performance guarantees of such algorithms have been extensively studied. For many problems we now have good approximation algorithms as well as strong (or even tight) complementary hardness results. This tutorial is an introduction to this subject, and we will discuss some of its central algorithmic and hardness results, leading up to its current frontiers.

On the algorithmic side, linear and semidefinite programming relaxations have been the most successful tool for designing good approximation algorithms for CSPs. We will discuss how to write canonical LP and SDP relaxations for CSPs, and see some examples of algorithms based on them and the non-trivial approximation ratios they are able to guarantee.

On the hardness side, we will review the PCP theorem and state some strong non-approximability results obtained by reductions from a CSP called Label Cover. These results prove that many natural CSPs are approximation resistant, in that outputting a random assignment yields essentially the best possible approximation guarantee. We will discuss the notion of Dictatorship testing and its utility in the context of proving non-approximability results via reductions from a special form of Label Cover called Unique Games. For illustration, we will discuss a tight dictator test for the Boolean CSP consisting of 3-variable linear equations.

We will then discuss recent progress based on the ``Unique Games conjecture'' which is able to identify the approximation threshold of every CSP as the integrality gap of a natural semidefinite programming relaxation, using the simplest binary CSP, MaxCut, for illustration. Time permitting, we may draw a parallel with the algebraic dichotomy conjecture, and comment how --- under the Unique Games conjecture --- the approximability of a CSP is precisely governed by the existence of non-trivial approximate polymorphisms.

Back to top