Lecture: Complexity Theory
Winter Term 2018/2019
News
- October 4
- The first lecture will be held on Monday, the 15th of October at 9:45 in room IZ 358.
Organization
- The lecture will be held by Dr. Prakash Saivasan and Peter Chini.
- The dates for the lecture are:
-
The exercise classes will be held on:
- Wednesday, 13:15 - 14:45 in IZ 358.
Oral exams
For successfully finishing the module, you have to pass an oral exam. We will announce possible dates for the same here.Exercises
The exercise sheets will be made available here. Please hand in your solution in the box next to room 343 in the Institute for Theoretical Computer Science.Lecture Notes
We offerLecture notes (last updated on October 27, 2016)
that are currently incomplete. If you have questions or spot a bug in the notes, please contact Peter.Furthermore, there are handwritten notes for the topics of the course. They will be made available during the lecture period.
Contents of the Lecture
- Classical Complexity Theory:
- L and NL
- P and NP
- PSPACE
- Alternation and the Polynomial Hierarchy
- Oracle Turing Machines
- Parameterized Complexity Theory:
- Basics
- Bounded Search Trees
- Dynamic Programming
- Inclusion Exclusion
- Kernelization
- Iterative Compression
- Randomization
- Advanced Algorithmic Techniques in Parameterized Complexity:
- Measure and Conquer
- Treewidth
- Subset Convolution
- Polynomials and Sieves
- Crown Decomposition / Sunflower Lemma / Nemhauser and Trotter
- Cut and Count
- Local Treewidth
- Lower Bounds in Parameterized Complexity Theory:
- Exponential Time Hypothesis
- Intractable Problems and Hardness
Literature
The lectures will be based upon the following books and articles. Most of them are available online, the remaining ones can be found in the library.- M. Sipser: Introduction to the Theory of Computation. International Thomson Publishing, 1996.
- I. Wegener: Complexity Theory. Springer, 2005.
- D.C. Kozen: Automata and Computability. Springer, 1997.
- Goldreich: Computational Complexity. Cambridge, 2008.