Complexity Theory
Course page →Details
A 6-ECTS lecture with exercises on computational complexity theory, covering lower bounds on the resources required to solve computational problems.
My role: Taught the lecture and exercise classes.
Courses I have taught, tutored, or assisted with.
A 6-ECTS lecture with exercises on computational complexity theory, covering lower bounds on the resources required to solve computational problems.
My role: Taught the lecture and exercise classes.
A graduate introduction to algebraic and geometric complexity theory, following the first twelve chapters of Bläser and Ikenmeyer’s Introduction to Geometric Complexity Theory. The goal is to develop the algebraic, geometric, and representation-theoretic tools needed to study the permanent-versus-determinant problem and the border rank of matrix multiplication.
My role: Taught Boolean and arithmetic circuits, Waring rank, orbit closures, and introductory algebraic geometry. Designed and graded exercise sheets; conducted and graded the oral exam.
A rigorous introduction to computational complexity, from models of computation and basic complexity classes to reductions, NP-completeness, randomized computation, interactive proofs, cryptography, and fine-grained complexity.
My role: Gave a substitute lecture on the Immerman–Szelepcsényi theorem. Prepared and graded NP-hardness exercises and led exercise discussions.
A practical course on professional skills for computer scientists. It covers how to give research talks, scientific writing, ethics, visual communication and interface design, legal issues, and intellectual property. Students give practice talks, receive feedback, and complete writing assignments.
My role: Taught the “Giving a talk” component, with feedback on research talks, slide design, and answering questions.
A 5-ECTS graduate introduction to computational complexity theory: models of computation, time and space complexity, reductions and \(\mathsf{NP}\)-completeness, hierarchy theorems, space complexity, circuit complexity, randomized computation, and interactive proofs.
My role: Led exercise sessions, explained solutions, and graded exercise sheets.
A 5-ECTS graduate introduction to computational complexity theory: models of computation, time and space complexity, reductions and \(\mathsf{NP}\)-completeness, hierarchy theorems, space complexity, circuit complexity, randomized computation, and interactive proofs.
My role: Led exercise sessions, explained solutions, and graded exercise sheets.
An advanced course on recent topics in geometric complexity theory, including connections to tensor rank and matrix multiplication.
My role: Led exercise sessions, prepared sample solutions, and graded exercise sheets.
An introduction to geometric complexity theory, the program initiated by Mulmuley and Sohoni to use algebraic geometry and representation theory to prove complexity lower bounds for explicit problems.
My role: Led exercise sessions, prepared sample solutions, and graded exercise sheets.
An advanced course (2+1, 5 credits) on fine-grained complexity: a more precise view of the complexity of polynomial-time problems, with matching upper and lower bounds and connections between seemingly unrelated problems.
My role: Led exercise sessions, prepared sample solutions, and graded exercise sheets.
The course covers the design and analysis of efficient algorithms and data structures.
My role: Led exercise sessions and graded exercise sheets and the final exam.