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
Requirements
Prerequisites (description)
Course coordinators
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:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: