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ä)