News
Regular Lecture tomorrowWritten on 29.04.24 by Markus Bläser There will be a lecture tomorrow at the usual time (12:15) and place (HS 001) given by Harry. I hope to be back on stage on Thursday. |
First assignmentWritten on 26.04.24 by Markus Bläser As you already saw, we uploaded a first assignment. You can form teams in cms until Tuesday. The assignment submission will open afterwards and is then open until Thursday evening. We will have a small tutorial on Monday Apr 29 in SR 014 in E.1.3 starting at 8:30. I am still ill, so we did not prepare… Read more As you already saw, we uploaded a first assignment. You can form teams in cms until Tuesday. The assignment submission will open afterwards and is then open until Thursday evening. We will have a small tutorial on Monday Apr 29 in SR 014 in E.1.3 starting at 8:30. I am still ill, so we did not prepare anything. But you can ask questions. If you plan to attend on Monday, please drop Sagnik an email so that he does have to get up for 0 persons. |
No lecture tomorrowWritten on 24.04.24 by Markus Bläser I am still sick. There will be no lecture tomorrow. I will upload another old video instead. |
No lecture todayWritten on 23.04.24 by Markus Bläser Unfortunately, I got sick overnight. There will be no lecture today. I uploaded two videos. Please watch the proof of the Immerman Szelepcsényi Theorem (second half of the first and first half of the second video). Sorry for the mess. I will keep you posted about the Thursday lecture. |
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/Introduction to Theoretical Computer Science".
Time and Date:
- Tuesday, 12:15 - 14:00, E1.3 HS001
- Thursday, 10:15 - 12:00, E1.3 HS001
- First lecture: Tuesday, April 16
We plan to record the lectures.
Tutorials:
- Mon 8:30-10:00. Room SR 014. The first tutorial will be April 29!
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.