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
SprechzeitenNach Vereinbarung

Research Interests

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

  • Parameterized complexity
  • Efficient preprocessing
  • Computational complexity

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


Current lectures (WS 2016/17)

Upcoming lectures (SS 2017)

Lectures that are already planned for the coming term. Let me know as soon as possible about desired topics, in particular regarding the lab on parameterized complexity (see regular lectures below).

  • MA-INF 1211 - Parameterized Complexity
  • MA-INF 1216 - Fine-Grained Analysis of Algorithms

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.

  • MA-INF 1104 - Advanced 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.

  • MA-INF 1211 - Parameterized Complexity
  • MA-INF 1212 - Seminar Parameterized Complexity
  • MA-INF 1317 - Lab Parameterized Complexity

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.

  • MA-INF 1214 - Computational Complexity

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.

  • MA-INF 1216 - Fine-Grained Analysis of Algorithms

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

Institutional Duties

  • Member of the examination council
  • Deputy executive director (there are five)

Community service

Program/Steering committee participation

  • Member of the IPEC steering committee from 2015 to 2018. Chair of the committee since 2016.
  • PC member of BDAS 2017, ESA 2017, IPEC 2017, WG 2017

Paper/Grant reviewing

  • Served on a selection panel of the German Academic Exchange Service (DAAD)
  • Reviewed grant proposals for the German Academic Exchange Service (DAAD), the European Research Council (ERC), the Czech Science Foundation (GACR), and the Israel Science Foundation (ISF)
  • Journal reviewer for ACM Transactions on Algorithms, Discrete Applied Mathematics, Discrete Mathematics, Theoretical Computer Science, Evolutionary Computation, Information Processing Letters, Journal of the ACM, Operations Research Letters, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, and Theory of Computing Systems

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
staff/stefankratsch.txt · Zuletzt geändert: 2017/02/27 14:14 von kratsch