Written on 05.07.21 (last change on 05.07.21) by Markus Bläser

You can find details regarding the exams here:

No lecture on May 24.

Written on 19.05.21 by Markus Bläser

Due to the holiday, there will be no lecture on Monday, May 24.

There will be a new assignment sheet, but with fewer exercises.

Complexity Theory


Complexity theory is the science of classifying problems with respect to their usage of resources. Ideally, we would like to prove statements of the form “There is an algorithm with running time O(t(n)) for some problem P and every algorithm solving P has to use at least Ω(t(n)) time”. But as we all know, we do not live in an ideal world

This lecture builds upon "Grundzüge der Theoretischen Informatik".


Time and Date:

  • Monday, 10:15 - 12:00 (online)
  • Wednesday 8:15 - 10:00 (online)
  • First lecture: Wednesday, April 14

Lectures are live and will be recorded. The recordings will be made available after the lecture. The Zoom links are posted under "Materials".



  • Thu 8:15 to 10:00 (online)



There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments. You can submit assignments in groups of up to three persons.



There will be oral exams at the end of the semester.



"Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NP-completeness) is highly recommended.



There are many good books an the topic. Here is a selection:

  • Sanjev Arora and Boaz Barak, Computational Complexity - A Modern Approach, Cambridge University Press.
  • Oded Goldreich, Computational Complexity - A Conceptual Perspective, Cambridge University Press.
  • Uwe Schöning, Gems of Theoretical Computer Science, Springer.
  • Rüdiger Reischuk, Komplexitätstheorie (Band 1), Teubner.


Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.