Below you find information about
Changes will be announced under news.
Johan Håstad, <email@example.com>, 790 6289, rum 1435, no offical office-hours make agreement by email to meet.
Email is the preferred way to contact Johan.
The course is open to anyone but the target audience is D4, F4 and the MD-line of SU. The course assumes a working knowledge of efficient algorithms.
The goals of the courseThe goals of the course are
We use the book Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
For the more basic material the set of notes by Johan Håstad might be useful.
Will be discussed at the first lecture. As the number of lectures have been halved since the last time the course ran, some adjustments have to be made compared to previous years.
Probably we will have three sets of homework problems but this will be decied firmly at the first lecture.
Please note the Nada code of honor that applies to all our courses.