Lehrinhalte
computational complexity (models of computation, reducibility, hardness and completeness, approximability, randomised complexity, parameterised complexity)
Literature
Sanjeev Arora, Boaz Barak: Computational Complexity, Cambridge University Press; Christos Papadimitriou: Computational Complexity, Pearson; Vijay Vazirani: Approximation Algorithms, Springer; Jörg Flum, Martin Grohe: Parameterized Complexity; Springer
Voraussetzungen
linear algebra, mathematical maturity (participation without certification of prerequisites is possible)
computational complexity (models of computation, reducibility, hardness and completeness, approximability, randomised complexity, parameterised complexity)
Literature
Sanjeev Arora, Boaz Barak: Computational Complexity, Cambridge University Press; Christos Papadimitriou: Computational Complexity, Pearson; Vijay Vazirani: Approximation Algorithms, Springer; Jörg Flum, Martin Grohe: Parameterized Complexity; Springer
Voraussetzungen
linear algebra, mathematical maturity (participation without certification of prerequisites is possible)
- Lehrende: Kord Eickmeyer
Semester: ST 2022