Seminar: Complexity Theory


Winter term 2017/2018

reserve shelf of the chair i7 in the computer science library Copyright: © M. Ritzert


The topic of complexity theory are the fundamental boundaries of efficient computation. Complexity theory deals with "inherrent difficulties" of algorithmic problems. We do not ask how efficient a certain algorithm solves a problem, but instead how efficiently can this problem be solved in general. Here efficiency is mesured by the amount of resources required, such as computation time, memory or communication bandwidth.
A special difficultiy here is to compare different measures of resources and thus some questions arise like "can every algorithm using few memory be simulated by a time-efficient one?" or "Are randomized algorithms in principle more efficient than deterministic ones?".


This Seminar is addressed to bachelor as well as master students.

Knowledge of the topics from the basic courses "Data Structures and Algorithms" and "Computability and Complexity" is required for participation. The course "Complexity Theory" might be helpfull, but is not required.



The seminar-talks will be held in german or english.

Time and Place

This course is a block seminar at the end of the Semester.

Precise dates will be announced later.


Martin Grohe
Christof Löding



Each participant of the seminar will be assigned a specific topic, usually in form of a research paper or a book chapter. He or she is expected to give a talk of about 45-60 minutes about it and write a paper of about 5 pages summarising it.

The topics will be assigned in the first meeting of the seminar.


External Links