Prof. Dr. Stefan Kratsch

Büro	Universitä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> <cs.uni-bonn.de>
Sprechzeiten	Nach 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> <hu-berlin.de>.

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.
• PC member of BDAS 2017, ESA 2017, IPEC 2017, WG 2017

• PC member of IPEC 2015, MFCS 2014, STACS 2014, ISAAC 2013, FSTTCS 2012, and IPEC 2012

• 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