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
E-Mail kratsch@cs.uni-bonn.de
SprechzeitenNach Vereinbarung

Research Interests

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

  • Parameterized complexity
  • Efficient algorithms
  • Computational complexity

Current lectures

In the summer term of 2016 both „Parameterized Complexity“ (MA-INF 1211) and „Computational Complexity“ (MA-INF 1214) are offered. Despite the similar names these are fairly different lectures: PC is an algorithms-oriented lecture, and features only a small amount of hardness proofs when they are useful to show limitations of algorithms. CC is a complexity lecture containing essentially no algorithms, and focusing on the classification of problems as needing certain amounts of (usually) time or space to solving them.

SS 2016 Parameterized Complexity MA-INF 1211

  • 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term
  • Lecture: Wednesday 8-10 and Friday 12-14 in room III.03 of the LBH building
  • Exercise: Fr 8-10 in room E.08 of the LBH building
  • There are no necessary study achievements to be permitted to the oral exam. Nevertheless, active participation in both lecture and exercises is highly recommended.
  • In the exercise meetings, students will work in teams of two to solve exercises, while being assisted by the tutor. There will be one exercise set per lecture chapter.
  • 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.

SS 2016 Computational Complexity MA-INF 1214

  • 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term
  • Lecture: Wednesday 14-16 and Friday 14-16 in room III.03 of the LBH building. The lecture room is not available on three Wednesdays due to council meetings in III.03; in those weeks we will either use the exercise slot or use Friday 16-18 in room III.03.
  • Exercise: Mi 12-14 in room E.08 of the LBH building
  • There are no necessary study achievements to be permitted to the oral exam. Nevertheless, active participation in both lecture and exercises is highly recommended.
  • In the exercise meetings, students will work in teams of two to solve exercises, while being assisted by the tutor. There will be one exercise set per lecture chapter.
  • 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 Seminar Parameterized Complexity MA-INF 1212

  • The initial meeting is on Monday April 18 from 9-12 in room E.08 in the LBH building.
  • In the meeting all students will be assigned a scientific paper from the field of parameterized complexity that appeared recently in a journal or conference.
  • Each participant needs to prepare and present a talk about the assigned paper.
  • Talks should be prepared using latex beamer or powerpoint (or appropriate substitute).
  • All talks will be given at the end of the lecture period in one or two longer meetings.
  • During the lecture period it is strongly recommended (but not mandatory) to make two appointments for discussing your general understanding of the assigned paper (first appointment) and for discussing a first version of your talk slides (second appointment).
  • Prior knowledge of parameterized complexity is not required.

SS 2016 Lab Parameterized Complexity MA-INF 1317

  • We will meet every two weeks. The first meeting is on Monday April 18 from 9-12 in room E.08 in the LBH building.
  • Knowledge of parameterized complexity is not required.
  • The programming task will usually have a scientific motivation and may be the basis of a master thesis (but this is far from mandatory).
  • Independent of the concrete topic you should expect a certain amount of implementation work and subsequent experiments. At the end of the term there should be a short (20 min) presentation of the results. It may be necessary to familiarize yourself a little with some recommended reading.
  • The tasks will not be „set in stone“ meaning that you can contribute your own suggestions for how to proceed, e.g., regarding further goals, code optimizations, other target problems.
  • In principle, you may also suggest a topic to work on (preferably by email beforehand), but final decision on topics lies with the lecturer/tutor.
  • Please send an email to kratsch@cs.uni-bonn.de if you are interested in participating. (This is not mandatory but may be helpful for planning.)

Upcoming lectures

WS 2016/17 Logik und diskrete Strukturen BA-INF 011 (send email if you would like to be a tutor)

If you would like to be a tutor for this lecture please send an email to Mrs. Bertram.

WS 2016/17 Seminar Parameterized Complexity MA-INF 1212

SS 2017 Parameterized Complexity MA-INF 1211

SS 2017 Lab Parameterized Complexity MA-INF 1317 (send email if you want a lab in WS 2016/17!)

It is intended to have the lab every summer. If you would like to take the lab in the winter term then contact me by email.

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

Scientific activities

Program/Steering committee participation

Current:

* Member of IPEC steering committee from 2016 to 2019

Previous:

Publications

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

staff/stefankratsch.txt · Zuletzt geändert: 2016/05/24 08:44 von kratsch

Benutzer-Werkzeuge