Algorithmic Model Theory 1000-2M24ATM

1. The problem of evaluating logical formulas on graphs – computational complexity
2. Graphs of bounded treewidth and bounded clique-width; evaluation of MSO formulas
3. Locality of First-order logic
4. Graphs of bounded maximum degree; evaluation of first-order formulas
5. Graphs of bounded local treewidth
6. Nowhere dense graph classes; evaluation of first-order formulas
7. Monadically stable and monadically NIP graph classes
8. Elements of combinatorics of set systems – Vapnik-Chervonenkis dimension, Sauer-Shelah Lemma, Welzl orders

Course coordinators

Szymon Toruńczyk

Requirements

Discrete mathematics

Prerequisites (description)

(in Polish) Wiedza z przedmiotów Logika dla Informatyków 1000-217bLOG oraz Grafy Rzadkie 1000-2M12GRZ będzie pomocna w niektórych częściach materiału, ale nie jest wymagana.

Assessment criteria

Homework (50%) and oral exam (50%).

The course can provide credit for doctoral students as a "methodological course". In that case, there is an additional requirement for passing the course: the student should correctly solve at least one of the more difficult problems from homeworks, designated by the instructors as a "research problem".

Bibliography

Szymon Toruńczyk, Lecture Notes in Finite Model Theory
Martin Grohe, Stephan Kreutzer, Methods for Algorithmic Meta Theorems
Notes and publications pointed by the lecturer

Additional information

Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes: