News
Lecture and tutorial will be switchedWritten on 07.02.23 by Markus Bläser The last lecture of the semester will be during the tutorial time, Thu Feb 09, at 10:15. |
Submission of assignmentsWritten on 20.01.23 by Markus Bläser As discussed today, we shift the submission dates by one week: Assignment 8 is due Jan 27 and Assignment 9 is due Feb 03. Consequently, there will be no tutorial on Jan 26. |
Energy saving weeksWritten on 15.12.22 by Markus Bläser Since the university is closed, there will be no physical lectures between December 19 and January 6. There will be online lectures via Zoom, you can find the link in the materials section. Lectures will be on
Since the university is closed, there will be no physical lectures between December 19 and January 6. There will be online lectures via Zoom, you can find the link in the materials section. Lectures will be on
All lectures will be recorded and made available as usual. There will be no tutorials between December 19 and January 6. The next tutorial is Jan 12 at 10:15. The solution of the assignment that is due tomorrow (I have just opened the submission... eh) will be discussed in this tutorial. The next assignment sheet will be released on Jan 6 (remind me if I forget) and is due Jan 13. There will be some problem sets, for those who start getting bored over Christmas. They are 100% voluntary. No points, pure pleasure...
|
No live lectures next week (Nov 15 and 18)Written on 11.11.22 by Markus Bläser As announced today, there are no live lectures next week. There are two videos in the materials section on chapter 8 (NP) and 11 (PSPACE). Please watch them next week or read the corresponding chapters in the script. (I have chosen chapters 8 and 11, because I think they are the most accessible ones.)… Read more As announced today, there are no live lectures next week. There are two videos in the materials section on chapter 8 (NP) and 11 (PSPACE). Please watch them next week or read the corresponding chapters in the script. (I have chosen chapters 8 and 11, because I think they are the most accessible ones.) When I am back, we will go on with chapter 6.
There will be a live tutorial on Thursday (HS001 in E1.3 at 10:15). There will be a new assignment sheet on Friday. |
Room change tutorial tomorrow (Nov. 10)Written on 09.11.22 by Markus Bläser The tutorial tomorrow will take place in seminar room SR 5 (011) in E2 4 in the math building, strictly speaking in the cellar connecting the math building to the math lecture halls. (Take the stairs down in the math building, this room is also known as "Der Bunker".) From next week on, the… Read more The tutorial tomorrow will take place in seminar room SR 5 (011) in E2 4 in the math building, strictly speaking in the cellar connecting the math building to the math lecture halls. (Take the stairs down in the math building, this room is also known as "Der Bunker".) From next week on, the tutorial will be in HS001 in E1.3 (the usual lecture hall).
|
Tutorial and AssignmentsWritten on 02.11.22 by Markus Bläser - Last Friday, we decided that we will vote for the tutorial slot on this Friday, Nov 4. - We shifted the submission deadline for the first assignment by one week. It is now Nov 11. - You can form teams in CMS until Nov 7. After this, the submission for the assignment solutions will open. -… Read more - Last Friday, we decided that we will vote for the tutorial slot on this Friday, Nov 4. - We shifted the submission deadline for the first assignment by one week. It is now Nov 11. - You can form teams in CMS until Nov 7. After this, the submission for the assignment solutions will open. - You can also hand in handwritten solutions during the lectures on Fridays. - I do not know the mysterious assistant either. - If you are looking for a challenge and want to be a tutor for the lecture while attending it, send your application |
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, 8:30 - 10:00, E1.3 HS001
- Friday, 12:15 - 14:00, E1.3 HS001
- First lecture: Tuesday, Oct 2
We plan to record the lectures.
Tutorials:
- Thursday, 10:15 - 12:00, E1.3 HS001
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.