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.

- MA-INF 1211 - Parameterized Complexity
- MA-INF 1216 - Fine-Grained Analysis of 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 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.

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.

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.

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

- Member of the IPEC steering committee from 2015 to 2018. Chair of the committee since 2016.

- 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)
- Conference subreviewer for COCOON, ESA, FOCS, FSTTCS, ICALP, IPEC, ISAAC, ISSAC, LATIN, SODA, STACS, STOC, SWAT, TAMC, and WG
- Journal reviewer for ACM Transactions on Algorithms, ACM Transactions on Computation Theory, Algorithmica, Artificial Intelligence, Discrete Applied Mathematics, Discrete Mathematics and Theoretical Computer Science, Evolutionary Computation, Information Processing Letters, Informs Journal on Computing, Journal of the ACM, Operations Research Letters, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, and Theory of Computing Systems

Since January 2015 | Professor for theoretical computer science at University of Bonn |

November 2012 - December 2014 | Junior research group leader at Technical University Berlin |

September 2012 - October 2012 | Postdoc at Max-Planck-Institute for Informatics |

September 2010 - October 2012 | Postdoc at Utrecht University working with Hans L. Bodlaender |

March 2008 - August 2010 | PhD student at Max-Planck-Institute for Informatics in Saarbrücken supervised by Kurt Mehlhorn |

October 2002 - February 2008 | Studies in Computer Science at Friedrich-Schiller University in Jena |

staff/stefankratsch.txt · Zuletzt geändert: 2017/04/10 14:17 von kratsch