Complexity Theory Markus Bläser, Balagopal Komarath

News

28.07.2018

Examination web page

Since the number of examinations exceeded what we can handle with pen and paper, we created a web page with the examination schedule. You need to log in to see it. Please let us know if something is wrong.

05.07.2018

Dates for oral exams

With very few exceptions, you can take your exam at any time between August 3 and October 12. Please let us know your preferred time by email. It would be nice if you could give us some interval of possible days, so that we have some flexibility when scheduling the... Read more

With very few exceptions, you can take your exam at any time between August 3 and October 12. Please let us know your preferred time by email. It would be nice if you could give us some interval of possible days, so that we have some flexibility when scheduling the exams.

 

04.06.2018

There will be no tutorial on Tuesday, June 5.

There will be no lecture on Wednesday, June 6.

There will be no new assignment on Wednesday, June 6.

You can hand in this week's solution on Monday, June 11, during the lecture.

 

09.05.2018

Assignment 4 is now online.

Deadline is next Wednesday.

29.04.2018

Due to the holiday, the tutorial for this week is moved to Thursday 3, 8:30 to 10:00, E1.3, SR016.

19.04.2018

The tutorials take place Tuesday 8:30 - 100 in  E1.3 SR016.

18.04.2018

The result that DTime1(o(n log n)) = DTime1(n) mentioned today in the lecture is Theorem 2 in:

  • Juris Hartmanis: Computational Complextiy of 1-tape Turing Machine Computations, Journal of the ACM, 15(2): 325-339, 1968.

The paper is rather old, so the... Read more

The result that DTime1(o(n log n)) = DTime1(n) mentioned today in the lecture is Theorem 2 in:

  • Juris Hartmanis: Computational Complextiy of 1-tape Turing Machine Computations, Journal of the ACM, 15(2): 325-339, 1968.

The paper is rather old, so the notation used there might be a little bit different from modern notation.

The only modern reference that I am aware of is unfortunately in German:

  • Rüdiger Reischuk: Komplexitätstheorie, Band I, Teubner (Theorem 3.1.8)
Show all
 

Complexity Theory

 

Time and Date:

  • Monday 10:15 - 12:00, E1.3 HS003
  • Wednesday 10:15 - 12:00, E1.3 HS003

First lecture will be on Wednesday, April 11!

 

Tutorials:

  • Tuesday 8:30 - 100, E1.3 SR016

 

Assignments:

There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments.

 

Exams:

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

Exam dates: We currently have exams on:

  • August 6,
  • August 30
  • September 3

If any of these dates suits you it would be nice to choose one from this list. Otherwise, please mail us your suggestion

 

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