Logic in Computer Science Prof. Dr. Martin Grohe

News

From now on, lectures will take place on Tuesdays from 9:15-10:45 and 11:15-12:45, and tutorials on Thursdays, 9:15-10:45, in room IV.424, John-von-Neumann-Bldg.

The exercises for the 15.6.2010 lecture can be found here.

The slides for the 15.6.2010 lecture can be found here.

The remaining slides for the 25.5.2010 lecture can be found here (*NEW*).

Introduction

Many important algorithmic problems are known to be NP-hard; it is unlikely that efficient (polynomial time) algorithms exist for these problems. Fixed-Parameter Tractability is one way to cope with the hardness of such problems. The idea is to restrict the seemingly unavoidable "combinatorial explosion" that leads to the exponential growth in the running time to certain problem specific parameters that tend to be small in practice. For many hard problems, this idea led to the design of fixed-parameter tractable algorithms that, albeit exponential in the worst case, are guaranteed to have an efficient running time in many practically important situations. Parameterized complexity theory complements this algorithmic approach by establishing the limitations of fixed-parameter tractability.

This course is an introduction to the main techniques for designing fixed-parameter tractable algorithms and the fundamentals of parameterized complexity theory. Lectures will be given in English.

Contents

1. Introduction to Fixed-Parameter Tractability
2. Algorithmic Techniques
   (Kernelizations, Bounded search trees, Color coding, Iterative compression, Dynamic programming and tree decompositions)
3. Complexity
   (Reductions and hard problems, the class W[P], the class W[1], kernel lower bounds)

Lecture Log

Brief notes about every lecture can be found here (after the lectures).

Lectures

Time and location

Tuesdays 9:00-11:00 and 11:00-13:00, Schrödinger Zentrum (Rudower Chaussee 26), room 1'306

 

Lecturers

Prof. Dr. Martin Grohe

Office hours: Thursdays 11:00 - 12:00

Dr. Paul Bonsma

Office hours: Tuesdays 14:00 - 15:00

Tutorials

In addition to the lectures there will be 2 hour tutorials.

Time and location

Thursdays, 9:15-10:45 John-von-Neumann-Bldg (Rudower Chaussee 25), room IV.424

 

Tutor

Dipl.-Math. Kord Eickmeyer

Exercises

There will be weekly exercise sets. Completing these successfully (at least 40% of all points) is necessary for receiving the course credit ("Schein") and admittance to the examination.

• Exercise Sheet 1 (15/4/2010; due 22/4/2010)
• Exercise Sheet 2 (4/5/2010; due 11/5/2010)
• Exercise Sheet 3 (11/5/2010; due 18/5/2010)
• Exercise Sheet 4 (18/5/2010; due 27/5/2010)
• Exercise Sheet 5 (25/5/2010; due 1/6/2010)
• Exercise Sheet 6 (1/6/2010; due 8/6/2010)
• Exercise Sheet 7 (8/6/2010; due 15/6/2010)
• Exercise Sheet 8 (15/6/2010; due 24/6/2010)
• Exercise Sheet 9 (29/6/2010; due 6/7/2010)

Examination

In the beginning of the semester break there will be oral examinations. For admittance to these examinations at least 40% of the exercise points are necessary.

Literature

The lectures will mainly be based on the following two books.

In addition the following book is recommended: