T-79.5103 Computational Complexity Theory

Tentative schedule (Autumn 2005)

Period I

Lecture 1 (14.9.2005)

Introduction (TJ)
Chapter 1: Problems and algorithms (TJ)

Lecture 2 (15.9.2005)

Chapter 2: Turing machines (TJ)

Lecture 3 (21.9.2005)

Chapter 2: More about Turing machines (TJ)
Chapter 3: Undecidability (TJ)

Lecture 4 (28.9.2005)

Chapter 4: Boolean logic (TJ)
Chapter 7: Complexity classes (TJ)

Lecture 5 (29.9.2005)

Chapter 7: Relations between Complexity classes (TJ)
Chapter 8: Reductions (TJ)

Lecture 6 (6.10.2005)

Chapter 8: Completeness (TJ)

Lecture 7 (12.10.2005)

Chapter 9: NP-complete problems (TJ)

Lecture 8 (13.10.2005)

Chapter 9: NP-complete problems - cont'd (TJ)

Lecture 9 (19.10.2005)

Chapter 10: coNP and function problems (TJ)

Seminar Talk Lottery (Thursday, 20.10.2005, 10:15)

Period II

Lecture 10 (2.11.2005)

Chapter 11: Randomized computation (seminar talks)
S1: pp. 241-248 (E. Parviainen)
S2: pp. 248-256 (M. Harva)

Lecture 11 (3.11.2005)

Chapter 11: Randomized computation (seminar talks)
S3: pp. 256-263 (Y. Yang)
S4: pp. 263-271 (A. Chauveau)

Lecture 12 (9.11.2005)

Chapter 12: Cryptography (seminar talks)
S5: pp. 279-287 (Z. Kovacs)
S6: pp. 287-293 (F. Morreale)

Lecture 13 (16.11.2005)

Chapter 13: Approximability (seminar talks)
S7: pp. 299-307 (H. Ren)
S8: pp. 307-315 (T. Hasu)

Lecture 14 (17.11.2005)

Chapter 13: Approximability
S9: pp. 315-322 (TJ)
Chapter 14: On P vs. NP (seminar talks)
S10: pp. 329-335 (A. Nevalainen)

Lecture 15 (23.11.2005)

Chapter 14: On P vs. NP (seminar talks)
S11: pp. 336-342 (M. Virtanen)
S12: pp. 343-349 (J. Lampiselkä)

Lecture 16 (24.11.2005)

Chapter 15: Parallel computation (TJ)
Chapter 16: Log space (TJ)

Lecture 17 (30.11.2005)

Chapter 17: The polynomial hierarchy (seminar talks)
S13: pp. 411-418 (E. Fagerholm)
S14: pp. 418-424 (K. Kinnunen)

Lecture 18 (1.12.2005)

Chapter 17: The polynomial hierarchy (seminar talks)
S15: pp. 424-432 (E. Linnanto)
Chapter 18: Computation that counts (seminar talks)
S16: pp. 439-447 (V. Vaskelainen)

Lecture 19 (7.12.2005)

Chapter 18: Computation that counts (seminar talks)
S17: pp. 447-451 (transferred to Jan 5, 2006)
Chapter 19: Polynomial Space (seminar talks)
S18: pp. 455-462 (X. Xie)

Lecture 20 (8.12.2005)

Chapter 19: Polynomial Space (seminar talks)
S19: pp. 469-475 (X. Xiao)
S20: pp. 480-486 (C. Della Monica)
Course summary and feedback session

Extra seminar session (5.1.2006, 10-12)

Chapter 18: Computation that counts (seminar talks)
S17: pp. 447-451 (M. Chowdhury)
Chapter 20: A Glimpse Beyond (seminar talks)
S21: pp. 491-498 (J. Yrjölä)