Seminar Selected Topics in Complexity Theory

This seminar is mainly addressed to Master students in computer science with a strong interest in theoretical computer science and, in particular, complexity theory. The seminar covers selected results (in form of papers or book chapters) related to complexity theory (e.g, on counting complexity, circuit complexity, fine-grained complexity, etc). Each seminar participant receives a topic (in form of a research paper or book chapter) that they will present in a roughly 30-40 minute talk, and 5-6 page report. The seminar is organized as a block seminar (most likely in February; precise dates will be determined later).

Registration:

To register for this seminar, please complete the poll available at https://bildungsportal.sachsen.de/umfragen/limesurvey/index.php/322922?lang=en by October 18, 2026. Seminar places for the module INF-25-Ma-FTK-Sem “Seminar Theoretical Computer Science and Symbolic AI" will be assigned based on the preferences indicated in this form.

First Meeting:

The first meeting is planned for the week 19-23 Oct (the exact date will be announced soon). During this meeting, the organization of the seminar is discussed and available topics are briefly presented.

Prerequisites:

Successful completion of basic courses on "Algorithmen und Datenstrukturen", "Automaten- und Berechenbarkeitstheorie" and "Logik und Komplexität".

Examination:

A written summary of 5-6 pages, and a presentation of roughly 30-40 minutes.