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.