Theoretical Computer Science

Lecture: Complexity Theory

Winter Term 2021/2022

News

04. Oktober

Die Veranstaltung beginnt mit einem Kick-Off Meeting am 26. Oktober um 12:30 Uhr.

26. Oktober

Das Kick-Off findet im BBB statt.

08. November

Die Übungen finden Dienstags um 13:15 im BBB statt. Die erste Übung ist am 16. November.

Organization

• Die Übung wird von Sören van der Wall, Thomas Haas und Rene Maseli betreut.
• Diese Vorlesung wird als Selbststudium angeboten. Das heißt, es wird keine Videos oder Präsenzlehre geben. Die Materialien zur Vorlesung werden hier aber angeboten und es gibt Übungsblätter und Übungstermine.
• Die Hausaufgabenabgabe erfolgt online, die Aufgaben werden in den Übungen besprochen. Scannen Sie dazu ihre handschriftlichen Hausaufgaben ein oder erstellen Sie diese direkt in digitaler Form als .pdf (z.B. mit LateX), und laden diese hoch. Ein entsprechender Abgabelink ist auf den Hausaufgabenblättern selbst zu finden. Falls Bedarf an einer physikalischen Abgabe (Abgabekästen im Informatikzentrum) besteht, wenden Sie sich bitte an Sören van der Wall.
• Als Kommunikationskanal dient Rocket Chat.
• Falls Sie die Vorlesung in den Bachelor einbringen möchten, klären Sie dies bitte mit dem Prüfungsamt ab.

Modul

Um das Modul erfolgreich abzuschließen, sind zwei Leistungen zu erbringen:

• Prüfungsleistung: Zu erbringen durch Bestehen einer mündlichen Abschlussprüfung zu Beginn des vorlesungsfreien Zeitraums. Das genaue Prüfungsdatum wird zeitnah bekannt gegeben.
• Studienleistung: Zu erbringen durch das erfolgreiche Bearbeiten von mindestens 50% der Übungsaufgaben.

Vorlesungsmaterial

Vorlseungsunterlagen (last updated on October 27, 2016)

Die Vorlesungsunterlagen sind nach Wochen aufgeteilt hier hochgeladen. Die Übungsblätter beziehen sich auf die Unterlagen zur jeweiligen Woche.

Woche 1 (01. November)

• Lower bounds via crossing sequences
• Time and Space Complexity Classes
• Alphabet reduction, tape reduction, compression, speed-up

Woche 2 (08. November)

• Space vs. time, non-determinism vs. determinism
• Savitch's theorem

Woche 3 (15. November)

• Space and time hierarchy results
• Translation theorems
• Immerman and Szelepcsényi's theorem

Woche 4 (22. November)

• Summary of the relationship among the robust complexity classes
• L and NL
• Models of computation for L and NL

Woche 5 (29. November)

• P and NP
• PSPACE

Woche 6 (06. Dezember)

• Alternation
• Alternation (contd.), the polynomial hierarchy

Woche 7 (13. Dezember)

• Oracle Turing machines, relativized complexity classes, and a characterization of the polynomial hierarchy
• Families of Boolean circuits
• Parallel complexity

Woche 8 (10. Januar)

• Parameterized complexity
• Bounded search trees

Woche 9 (17. Januar)

• Kernelization
• Principle of inclusion and exclusion

Woche 10 (24. Januar)

• Iterative compression
• Dynamic programming

Woche 11 (31. Januar)

• Randomized parameterized algorithms and derandomization (color coding)
• Algebraization

Woche 12 (07. Februar)

• Fast subset convolution

Woche 13 (14. Februar)

• Treewidth (Part 1)
• Treewidth (Part 2)

Exercise Sheets

Zur Abgabe bitte den Upload-Link am Ende des Blattes verwenden.

• Exercise Sheet One
• Exercise Sheet Two
• Exercise Sheet Three
• Exercise Sheet Four
• Exercise Sheet Five
• Exercise Sheet Six
• Es gibt keine Aufgaben zu Woche 10.
• Exercise Sheet Seven (Derandomization)
• Exercise Sheet Eight
• Exercise Sheet Nine

Additional Material

• Basics on Fixed-points (Chapter 1 of the script)
• Parameterized complexity
• Scheduling and jump number
• Nemhauser and Trotter's theorem
• Hardness in parameterized complexity
• Advanced topics in parameterized complexity

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.