Prof. Dr. Stefan Kratsch

BüroUniversität Bonn
Institut für Informatik I
Raum II.60
Friedrich-Ebert-Allee 144
D-53113 Bonn
Telefon+49 (228) 73 - 4554
Fax +49 (228) 73 - 4321
E-Mail <lastname> <at> <>
SprechzeitenNach Vereinbarung

News: I have moved to Humboldt University Berlin on September 1, 2017. This website will no longer be updated. You can contact me at <firstname> <dot> <lastname> <at> <>.

Research Interests

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

An up to date list of my publications can be found using the awesome complete search interface for DBLP.


Current lectures (SS 2017)

Regular lectures (repeated yearly or bi-yearly)

Advanced Algorithms

Advanced Algorithms is a yearly lecture that was started in 2015. It covers algorithmic techniques that usually go beyond Bachelor level material, e.g., techniques from approximation algorithms, exact exponential-time algorithms, and randomized algorithms.

The lecture is given yearly in the winter term, though not always by Prof. Kratsch.

Parameterized Complexity

Parameterized Complexity is my main research area. This field seeks to find non-trivial algorithms for NP-hard problems that may be viable if certain problem parameters are small. The lecture gives an introduction to the area, focusing on algorithmic techniques but covering also notions of hardness.

The lecture is given yearly in the summer term. Seminar and lab are offered at least yearly, and you are encouraged to get in contact as early as possible (by email) if you are interested in taking either, so that they can be scheduled in the next term. For the lab, in particular, you should feel strongly encouraged to suggest rough ideas, general interests, or concrete ideas for things that you would like to explore.

Computational Complexity

The lecture on Computational Complexity gives an introduction to classical complexity, following roughly the first third of „Computational Complexity: A Modern Approach“ by Arora and Barak.

The lecture is given bi-yearly in the summer term.

Fine-Grained Analysis of Algorithms

This lecture focuses on the recent and highly active topic of establishing tight lower bounds for polynomial-time algorithms. Most results of this type are based on hypotheses about the optimality of algorithms for certain key problems such as 3-SUM or Satisfiability.

The lecture is given bi-yearly in the summer term.

Institutional Duties

Community service

Program/Steering committee participation


Paper/Grant reviewing

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