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

- Parameterized complexity
- Efficient algorithms
- Computational complexity

**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:
- Turing machines
- NP and NP-completeness
- Diagonalization
- Space complexity
- The polynomial hierarchy and alternations
- Boolean circuits
- Randomized computation
- 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:
- 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)
- This is in contrast to the theory of NP-completeness which posits that Vertex Cover and Independent Set are equivalent under polynomial-time reductions.
- 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 |

* Member of IPEC steering committee from 2016 to 2019

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

An up to date list of my publications can be found at dblp.org.

en/staff/stefankratsch.txt · Zuletzt geändert: 2015/10/27 15:44 von kratsch