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

- Parameterized complexity
- Efficient algorithms
- Computational complexity

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:
- 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.

**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:
- 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 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.)

**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**

**WS 2016/17 Lab Parameterized Complexity MA-INF 1317**

Sending an email beforehand (possibly now) is appreciated but not necessary. It may help planning of the lab's content, and you may be able to influence that by indicating some interests that you may have. The topic „parameterized complexity“ is interpreted quite flexibly.

**SS 2017 Parameterized Complexity MA-INF 1211**

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.

staff/stefankratsch.txt · Zuletzt geändert: 2016/05/31 15:40 von kratsch