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

• explain the fundamental concepts behind algorithmic meta-theorems
• explain, assess, and analyze the discussed algorithms
• model and analyze unknown problems in order to apply a meta-theorem 

An algorithmic meta-theorem states that if a problem can be formulated in a certain logical framework, it can be solved efficiently on a certain class of problem inputs. Hence, algorithmic meta-theorems allow formulating general results beyond individual problems and use logical methods to capture whole families of problems at once. In this course, several algorithmic meta-theorems will be considered. It will be discussed how the theorems can be established and how they can be applied to individual problems.

Some of the topics covered by the course:

• Solving problems definable in first-order logic on sparse graphs.
• Solving problems definable in monadic second-order logic on tree-like graphs.
• Gaifman's theorem and Feferman-Vaught's theorem.

The core of the course consists of a series of lectures that explore topics in the studied area. The lectures are held in an informal, seminar-like setting and are interactive - students are expected to to engage in what's going on actively. Every new method and technique introduced during the lecture is demonstrated in several examples.

The lectures take place in room FAV 01 A and the exercises take place in room FAV 01 B. The course is planned to be held in person. We switch to online if the covid situation requires it.

Exercises plus oral exam.

Bachelor-level knowledge of graph theory, discrete algorithms and logic is assumed.