Prof. Dr. Stefan Kratsch

OfficeUniversity of Bonn
Institute of
Computer Science, Dept. I
Room II.60
Friedrich-Ebert-Allee 144
D-53113 Bonn
Phone+49 228 73 4554
Fax +49 (228) 73 - 4321
Office Hoursby appointment

Research Interests

My main research interests are the following topics of theoretical computer science.

  • Parameterized complexity
  • Efficient algorithms
  • Computational complexity

Current lectures

Upcoming lectures

SS 2016: Computational Complexity (tentative)

  • 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term
  • Lecture is based on „Computational Complexity: A Modern Approach“ by Sanjeev Arora and Boaz Barak.
  • Topics:
    1. Turing machines
    2. NP and NP-completeness
    3. Diagonalization
    4. Space complexity
    5. The polynomial hierarchy and alternations
    6. Boolean circuits
    7. Randomized computation
    8. As time permits: Interactive proofs, Cryptography, PCP theorem and hardness of approximation

SS 2016 Parameterized Complexity (tentative)

  • 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term
  • Parameterized complexity takes an alternative, more fine-grained perspective on NP-hard/complete problems:
    1. Example: It is significantly easier to determine whether a graph has a vertex cover of size at most k (a set of vertices touching all edges) than to tell whether it has an independent set of size at least k (a set of vertices that are mutually non-adjacent)
    2. This is in contrast to the theory of NP-completeness which posits that Vertex Cover and Independent Set are equivalent under polynomial-time reductions.
    3. The crux in this difference lies in insisting on a small value of the solution size k. Such parameters can strongly impact the time and space needed to solve hard problems.
  • The lecture introduces a diverse toolbox of algorithmic techniques with which a variety of problems can be tackled.
  • We will also discuss tools for establishing that certain parameterized algorithms are likely to be optimal in runtime.

Brief Curriculum Vitae

Since January 2015Professor for theoretical computer science at University of Bonn
November 2012 - December 2014Junior research group leader at Technical University Berlin
September 2012 - October 2012Postdoc at Max-Planck-Institute for Informatics
September 2010 - October 2012Postdoc at Utrecht University working with Hans L. Bodlaender
March 2008 - August 2010PhD student at Max-Planck-Institute for Informatics in Saarbrücken supervised by Kurt Mehlhorn
October 2002 - February 2008Studies in Computer Science at Friedrich-Schiller University in Jena

Scientific activities

Program/Steering committee participation


* Member of IPEC steering committee from 2016 to 2019



An up to date list of my publications can be found at

en/staff/stefankratsch.txt · Zuletzt geändert: 2015/10/27 15:44 von kratsch