# 192.122 Algorithmic Meta-Theorems This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2023W 2022W 2021W

2022W, VU, 2.0h, 3.0EC

## Properties

• Semester hours: 2.0
• Credits: 3.0
• Type: VU Lecture and Exercise
• Format: Hybrid

## Learning outcomes

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

## Subject of course

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.

## Teaching methods

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.

## Mode of examination

Immanent

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.

## Course dates

DayTimeDateLocationDescription
Tue11:00 - 13:0011.10.2022 - 20.12.2022Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri11:00 - 13:0021.10.2022 - 16.12.2022Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Thu16:00 - 18:0015.12.2022Seminarraum FAV EG B (Seminarraum von Neumann) research
Algorithmic Meta-Theorems - Single appointments
DayDateTimeLocationDescription
Tue11.10.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Tue18.10.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri21.10.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue25.10.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri28.10.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri04.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue08.11.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri11.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri18.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue22.11.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri25.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue29.11.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri02.12.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue06.12.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri09.12.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue13.12.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Thu15.12.202216:00 - 18:00Seminarraum FAV EG B (Seminarraum von Neumann) research
Fri16.12.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue20.12.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture

## Examination modalities

Exercises plus oral exam.

## Course registration

Begin End Deregistration end
22.09.2022 19:00 03.11.2022 19:00 20.11.2022 19:00

## Curricula

Study CodeObligationSemesterPrecon.Info
066 931 Logic and Computation Mandatory elective
066 937 Software Engineering & Internet Computing Not specified

## Literature

No lecture notes are available.

## Previous knowledge

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

English