## DD2446 Complexity theoryBelow you find information about
Changes will be announced under news.
## Schedule
## ProfessorJohan Håstad, <johanh@kth.se>, 790 6289, rum 1435, no offical office-hours make agreement by email to meet. Email is the preferred way to contact Johan. ## Who may take the courseThe 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
- to give an overview of modern complexity theory
- understand the notions of complexity classes and complete problems
- be able to prove statements in complexity theory,
- be able to read (simple) research papers in complexity theory.
## Course material## BookWe 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. ## Short overviewWill 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. ## ExaminationProbably 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. |