SUBJECT
Title
Complexity theory
Type of instruction
lecture + practical
Level
master
Faculty
Part of degree program
Credits
3+3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
A short description of the course: finite automata, Turing machines, Boolean circuits. Lower bounds to the complexity of algorithms. Communication complexity. Decision trees, Ben-Or’s theorem, hierarchy theorems. Savitch theorem. Oracles. The polynomial hierarchy. PSPACE. Randomized complexity classes. Pseudorandomness. Interactive protocols. IP=PSPACE. Approximability theory. The PCP theorem. Parallel algorithms. Kolmogorov complexity.
Readings
- László Lovász: Computational Complexity (ftp://ftp.cs.yale.edu/pub/lovasz.pub/complex.ps.gz)
Further reading:
- Papadimitriou: Computational Complexity (Addison Wesley, 1994)
- Cormen. Leiserson, Rivest, Stein: Introduction to Algorithms; MIT Press and McGraw-Hill.