Algebraic and Model Theoretical Methods in Constraint Satisfaction (14w5136)


Manuel Bodirsky (TU Dresden)

(Simon Fraser University)

(University of Leeds)

(Charles University, Prague)


The Banff International Research Station will host the "Algebraic and Model Theoretical Methods in Constraint Satisfaction" workshop from November 23rd to November 28th, 2014.

The aim in a constraint satisfaction problem (CSP) is to find an
assignment of values to a given set of
variables, subject to constraints on the values which can be assigned
simultaneously to certain specified
subsets of variables. CSPs are used to model a wide variety of
computational problems in computer science,
discrete mathematics, artificial intelligence, and elsewhere, and they
have found numerous applications in
those areas. Several very successful approaches to study the
complexity and algorithms for constraint
satisfaction problems have been developed over the last decade. One of
the most fruitful uses universal
algebra. So far the bulk of research on the CSP has been done assuming
the variables can take only a finite
number of values. The infinite CSP, in which this restriction is
removed, has much stronger expressive
power, but is also much harder to study. Two recent discoveries made
it possible to transfer some
techniques, in particular the algebraic approach, from the finite to
some classes of the infinite CSP.
The goal of this workshop is for the first time to bring together
researchers from model theory,
topological dynamics, combinatorics, universal algebra, and computer
science to explore the implications of this new connection between
these three fields.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).