News

Upcoming tutorial postponed by a day

Written on 03.07.24 by Sanyam Agarwal

Hi,
The upcoming tutorial will be held on Tuesday 8:30am, instead of Monday. I apologise for the inconvenience this might cause. In case you are unable to attend, you can send me an email, or drop by in my office (E1 3 421).
Best,
Sanyam

Tutorial postponed

Written 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 8

Written on 13.06.24 by Harry Zisopoulos

Assignment 8 is now online. 

Assignment 7

Written 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 more

Written 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 TUESDAY

Written 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 3

Written on 10.05.24 (last change on 10.05.24) by Harry Zisopoulos

Assignment 3 is now uploaded. Please do not forget to upload your solutions to Assignment 2 if you haven't done so already.     Apologies, did not see the deadline lapsed on midnight. 

Regular Lecture tomorrow

Written 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 assignment

Written 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 tomorrow

Written 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 today

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

Show all

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.

 

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