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

Arriving in Banff, Alberta Sunday, November 23 and departing Friday November 28, 2014


Manuel Bodirsky (Technische Universität Dresden)

(Simon Fraser University)

(University of Leeds)

Jaroslav Nesetril (Charkes University)


This workshop will for the first time bring together researchers from model theory, universal algebra, and computer science to explore the implications of the new connection between these three fields fostered by advances in infinite domain constraint satisfaction problems.

The workshop will focus on the following main goals.

(1) Recent advances in computational and descriptive complexity of finite domain constraint satisfaction, in particular, new results and hopes towards the dichotomy conjecture and finer complexity classification of CSPs.

(2) Progress in the study of finite CSPs has boosted research in universal algebra. We will exchange ideas and results that help to use CSP methods to advance universal algebra.

(3) During the last few years the research of CSPs with mixed restrictions and problems related to the CSP has intensified. We plan to discuss new directions and perspectives of finite domain CSPs.

(4) Further generalization of the universal-algebraic approach from finite to infinite domains, in particular when the constraint language of a CSP is omega-categorical. A particular question in this context asks which infinite domain CSPs have bounded width, i.e., are polynomial-time tractable via local consistency techniques.

(5) Complexity classifications for important classes of infinite domain CSPs, such as set constraint languages, branching-time constraint languages, or interval constraint languages.

(6) Applications of Ramsey theory for the classification of homogeneous structures and their reducts (up to both first order interdefinability and positive primitive interdefinability).

(7) Infinite domain CSPs in general do not admit a complexity dichotomy of polynomial time vs. NP-hardness. Explore the boundaries within which dichotomy results can be true; obtain more non-dichotomy results.

(8) Discussion of possible techniques for complexity classification for non-omega-categorical structures. In particular, find tractable expansions of linear programming and tractable restrictions of integer linear programming. Clarify the relationship between the max-atoms CSP (which is equivalent to mean payoff games) and other infinite domain CSPs of unknown complexity.