TCS / Studies / T-79.5103 Computational Complexity Theory
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science


Computational Complexity Theory

(5 cr) P

Autumn 2007 (periods I and II)

Previous years: [Autumn 2005] [Autumn 2006]

This is an advanced course on computational complexity covering topics such as NP-completeness, randomized algorithms, cryptography, approximation algorithms, parallel algorithms, polynomial hierarchy, PSPACE-completeness.

General Information

  • (17.1.) NEWS: Final grading summary available below.
  • Please use the WebTOPI system for registration.
  • This course replaces the former course T-79.240 Special Course in Computational Complexity.
  • Lectures: Prof. Ilkka Niemelä, Mondays, 10-12, and Wednesdays, 10-12, room TB353 (see the lecture program for exceptions).
  • Tutorials: Lic.Sc.(Tech.) Matti Järvisalo, Mondays, 14-16, room TB353 (see the tutorial program for exceptions).
  • The course starts on Mon Sep 17 at 10 o'clock in TB353.
  • Course material: C. Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
    (Errata from the publisher, some further corrections)
  • Brochure in Finnish
  • Grading: First part exam (20%), three home assignments (40%), second part exam (40%)
  • Summary of the grading in Autumn 2007 [pdf]

Course Program

Course Feedback

We welcome feedback which is collected centrally in Finnish, Swedish, and English. The questionnaire is open from December 10 to January 7, 2008.

  • To obtain a 0.5 point homework bonus you are supposed to fill in the form by January 7, 2007 (23:59 hours). Please remember to supply your student ID on the form. This is just to collect the list of students who have given feedback (anonymity is not otherwise compromised).
Back to menu.

Further Reading

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 17 January 2008. Ilkka Niemelä