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
