(*) We cannot use room LBH III.03 on three days during the semester when there is the institute council meeting (and Prof. Kratsch is also not free at that time). Instead we will have a double lecture on Friday during those weeks.

In addition to signing up via basis please send an email to kratsch@cs.uni-bonn.de to provide your email address (using „[Computational Complexity]“ as the subject). You will receive occasional notifications, (updates to) the lecture notes, and the exercise sheets via email. Note that sending an email is not equivalent to signing up on basis and comes with no obligations.

There will be an oral exam at the end of the term. There are no requirements for admittance and the final grade is determined solely by the exam.

In the tutorials you will be given time and support to solve exercises in teams of two. Eva-Maria Hols will be present in tutorials and answer your questions or give hints. There will be essentially no presentation of solved exercises since the focus is on solving things yourself. In particular, being able to explain a solution to your neighbor is highly beneficial, and being told that „this is actually quite easy“ is much more believable coming from your neighbor. We also found that (unsurprisingly?) students are much more apt at understanding one anothers problems with a task.

Exercise sets will focus on the current chapter in the lecture and you may have more than one meeting to work one the same set. Working at home is of course encouraged too. We will not grade or proof-read your solutions, but you can verify your ideas by asking Eva-Maria during the tutorial.

There are no prerequisites other than having completed a Bachelor (typically in mathematics or computer science) or being close to doing so. Standard Bachelor lectures about algorithm design/analysis, discrete structures, logic, complexity are nevertheless beneficial.

If you do not have your Bachelor yet then you need contact the examination office to sign up for the lecture. You can still only use the grade for this course towards your Master degree.

Printer friendly versions of the slides will be made available via email. Additional material such as proofs and illustrative sketches will be given on the board and you have to take notes yourself.

1. Turing machines
2. NP and NP-completeness
3. Diagonalization
4. Space complexity
5. The polynomial hierarchy and alternations
6. Boolean circuits
7. Randomized computation
8. As time permits: Interactive proofs, Cryptography, PCP theorem and hardness of approximation

The lecture is based on „Computational Complexity: A Modern Approach“ by Sanjeev Arora and Boaz Barak. We will focus on the first of its three parts. Further material can be suggested if desired.