T-79.5103 Computational Complexity Theory

Tentative schedule (Autumn 2006)

Period I

Lecture 1 (19.9.2006)

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

Lecture 2 (20.9.2006)

Chapter 2: Turing machines (IN)

Lecture 3 (26.9.2006)

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

Lecture 4 (27.9.2006)

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

First Quarter Exam (3.10.2006)

Lecture 5 (4.10.2006)

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

Note: No lectures on Tue 10.10.2006

Lecture 6 (11.10.2006)

Chapter 8: Completeness (IN)

Lecture 7 (17.10.2006)

Chapter 9: NP-complete problems (IN)

Lecture 8 (18.10.2006)

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

Lecture 9 (24.10.2006)

Seminar Talk Lottery (at 10:15)

Chapter 10: coNP and function problems (IN)

Note: Tutorials instead of lectures on Wed 25.10.2006

Period II

Lecture 10 (7.11.2006)

Chapter 11: Randomized computation (seminar talks)
S1: pp. 241-248 (Tuominen)
S2: pp. 248-256 (Kähkönen)

Lecture 11 (8.11.2006)

Chapter 11: Randomized computation (seminar talks)
S3: pp. 256-263 (Ihantola)
S4: pp. 263-271 (Launiainen)

Lecture 12 (14.11.2006)

Chapter 12: Cryptography (seminar talks)
S5: pp. 279-287 (Hällfors)
S6: pp. 287-293 (van der Meer)

Lecture 13 (15.11.2006)

Chapter 13: Approximability (seminar talks)
S7: pp. 299-307 (Pitkämäki)
S8: pp. 307-315 (Lindfors)

Note: No lectures on Tue 21.11.2006

Lecture 14 (22.11.2006)

Chapter 13: Approximability (seminar talks)
S9: pp. 315-322 (Hanhijärvi)
Chapter 14: On P vs. NP (seminar talks)
S10: pp. 329-336 (Heikinheimo)

Lecture 15 (27.11.2006)

This is on Monday at 14-16 in T-B353
Chapter 14: On P vs. NP (seminar talks)
S11: pp. 336-343 (Hakala)
Chapter 15: Parallel computation (IN)

Lecture 16 (28.11.2006)

Chapter 16: Log space (seminar talks)
S12: pp. 395-404 (Lahtinen)
Chapter 17: The polynomial hierarchy (seminar talks)
S13: pp. 411-418 (Lahola)

Lecture 17 (29.11.2006)

Chapter 17: The polynomial hierarchy (seminar talks)
S14: pp. 418-424 (Busch)
S15: pp. 424-432 (Viinamäki)

Note: No lectures on Tue 5.12. and Wed 6.12.2006

Lecture 18 (12.12.2006)

Chapter 18: Computation that counts (seminar talks)
S16: pp. 439-447 (Raitanen)
S17: pp. 447-451 (IN)

Lecture 19 (13.12.2006)

Chapter 19: Polynomial Space (seminar talks)
S18: pp. 455-462 (IN)
Chapter 20: A Glimpse Beyond (IN)
Course summary and feedback session