News
Upcoming tutorial postponed by a dayWritten on 03.07.24 by Sanyam Agarwal Hi, |
Tutorial postponedWritten on 14.06.24 by Sagnik Dutta Due to unavailability of the tutors on Monday, the upcoming tutorial will be held on Wednesday from 8:30 a.m. |
Assignment 8Written on 13.06.24 by Harry Zisopoulos Assignment 8 is now online. |
Assignment 7Written on 06.06.24 by Harry Zisopoulos Dear students, Assignment 7 is now online. Don't be intimidated by the number of pages, most of the (sub)exercises are for bonus points and only 12 points are non-bonus. If you did not attend Thursday's lecture and wish to solve exercise 7.3, you will find the first half of the lecture's recording… Read more Dear students, Assignment 7 is now online. Don't be intimidated by the number of pages, most of the (sub)exercises are for bonus points and only 12 points are non-bonus. If you did not attend Thursday's lecture and wish to solve exercise 7.3, you will find the first half of the lecture's recording quite useful. |
TUE-torial once moreWritten on 18.05.24 by Sagnik Dutta As Monday is a holiday, we will have the tutorial on Tuesday again this week from 8:30. |
Tutorial on TUESDAYWritten on 11.05.24 by Sagnik Dutta I am out of town on Monday. We will have the tutorial on Tuesday instead (only for this week) from 8:30 a.m. Hope that works out for most of you. If you are not able to attend and have questions regarding the assignment, feel free to drop by any time at my office room E1 4 - 327. |
Assignment 3Written on 10.05.24 (last change on 10.05.24) by Harry Zisopoulos Assignment 3 is now uploaded. |
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.
The exams can be at any time between the last week of the lecture period and end of October (provided that I am available). I will be on holiday from July 29 to August 9.
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.