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

Until this webpage is fully set up please refer also to my old homepage at TU Berlin.

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

• Parameterized complexity
• Efficient algorithms
• Computational complexity

SS 2015 Seminar on Parameterized Complexity

• We will have the first meeting in the second week of the lecture period on Monday April 13 at 14:30-16:00 in room S.08 of the LBH building.
• During this first and maybe a second meeting each participant will receive a paper about which he/she will give a talk at the end of the term.
• We will probably have a few longer meetings at the end of the term when the talks are given.
• Time slots after the initial meetings and before the talks will be used to discuss the paper/slides in preparation.
• It will be possible to follow enough of the lecture „Parameterized Complexity“ before giving a talk. Thus it is feasible to attend both seminar and lecture even if the topic is new to you.

SS 2015 Parameterized Complexity

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

WS 2015/16: Advanced Algorithms (tentative)

• 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term
• The lecture attempts to give an overview over a wide range of algorithmic topics beyond the scope of the bachelor algorithmic lectures.
• Nevertheless, some important topics will be briefly recapped to ease the start into this and maybe further algorithmic lectures in the computer science master.
• Topics (tentative):
  1. Flows, matchings, and linear programs
  2. Approximation algorithms
  3. Exact exponential-time algorithms
  4. Online algorithms
  5. Smoothed complexity analysis
  6. more to come!

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

* PC member of IPEC 2015

* PC member of 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.