Prof. Dr. Stefan Kratsch

Office	University 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
		Email	kratsch@cs.uni-bonn.de
Office Hours	by appointment

Research Interests

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

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.

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