After successful completion of the course, students are able to...

• explain the theory and algorithms necessary for understanding and solving constraint satisfaction problems

***********************************************************************************

The presentation with attendance of students had to be canceled.

Instead, videos of the lecture will be published via TUWEL. Stay tuned for further information regarding the where and when.

The lecturer of this course will be Prof. Miki Hermann (Ecole Polytechnique, France).

*************

The course was held in March 2020.

Constraint satisfaction problems (CSPs) naturally arise in various domains, like when assigning noninterfering frequencies, validating new CPUs, or designing schedules. Therefore it is necessary to develop a theory to assess the complexity of CSPs in a systematic way and delineate tractable (polynomial-time decidable) from non-tractable fragments. This theory also forms the basis of constraint programming.
The course will teach students the theory and algorithms necessary for understanding and solving constraint satisfaction problems. We will introduce CSPs parameterized by a set of relations over a given domain. In the first part, the course will focus on problems over the Boolean domain, then extend the results to finite domains, and finally finish with remarks concerning problems over infinite domains (integers, rationals, reals, . . . ).
The course will cover functional and relational clones, their relationship to classes of propositional formulas like Horn, dual Horn, bijunctive, affine, and complementive. Using methods from universal algebra, in particular Post’s lattice of clones, we will obtain a complete complexity classification in the form of Schaefer’s Dichotomy theorem.
We will also present so-called constraint description problems that search for formulas characterizing given data. This form of machine learning receives revived interest lately with the problems presented by big data.

Prerequisites: propositional logic, basics of complexity theory (decision problems, P, NP, coNP),
algorithm design and analysis

Presentations

Lecture videos for distance learning

Exercises

Written exam

This is a visiting professor course of the Vienna PhD School of Informatics

The solutions to the exercises as well as the written exam will be graded.

Please register in TISS.

See TUWEL for the course material.

Prerequisites:
propositional logic, basics of complexity theory (decision problems, P, NP, coNP), algorithm design and analysis