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".

 

Tutorials:

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

 

Assignments:

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.

 

Exams:

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

 

Prerequisites:

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

 

Literature:

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.