Complexity theory is the study of the amount of resources needed to solve computational problems on various models of computations. Typical models of computation are Turing machines (deterministic, non-deterministic, probabilistic), arithmetic circuits, or boolean circuits.

This advanced complexity theory course builds upon Prof. Kliesch's Computability and Complexity course and takes a deeper dive into the main areas in complexity such as circuit lower bounds,  space complexity, algebraic complexity, interactive proofs, and much more.

• Lecturer: Prof. Dr. Antoine Mottet
• Winter semesters
• Bachelor students in Technomathematik, Master students in Technomathematik, Master students in Computer Science
• 6 ECTS
• 2 meetings per week (1.5 hour lectures, 1.5 hour tutorials)

It is highly recommended to have followed the course Computability and Complexity given in summer semesters.

• Approximation
• Probabilistic algorithms
• Counting complexity
• Arithmetic complexity
• Interactive proof systems