Description of the course

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.

Course organisation

  • 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