[TU Dresden]


Technische Universität Dresden
Institut für Theoretische Informatik
Lehrstuhl für Automatentheorie

Hauptseminar theoretische Informatik: "Parameterized Complexity"

Position in Curriculum
Informatik (both diploma and bachelors degree), starting from 5. semester, Wahlpflichtveranstaltung (-/-/2)
Computational Logic: Modules TCSL and IT, 3 credit points

Basic knowledge in logic.
For computer scientist students: Pflichtvorlesung Grundlagen der Theoretischen Informatik.

The language of the seminar is English — unless attended by native German speakers only.

Preliminary schedule
The initial meeting will be on Tuesday October 19th at 16:40 (6. DS) in room INF 3027.

Number Speaker Chapter Partner paper Tutor Presentation Report due
1 Sergey Paramonov 4 No. 5 Rafael January 21 November 26
3 Ronald de Haan 3 No. 6 Felix January 21 December 3
5 Premchand Nutakki 5.2, 8.1-8.5 No. 4 Anni February 4 December 10
6 Ana Pavlisic 14 No. 2 Rafael February 4 December 17

The previous chapters refer to the book Parameterized Complexity Theory by J. Flum and M. Grohe.

Topic of the Hauptseminar
Complexity theory classifies decision problems according to the resources (time and space) necessary for solving them. In the standard setting, these resources are measured with respect to the whole input. However, for some families of problems it can be shown that the complexity depends only on a part (a parameter) of this input. Parameterized complexity deal with the study of the complexity of decision problems w.r.t. such parameters. If a problem is hard w.r.t. a given parameter, then it may still be efficiently solved if that parameter is adequatedly bounded.

Goal of the Hauptseminar
Apart from learning about the main topic, students should learn how to get acquainted with a relevant body of literature, how to produce a well-structured paper, and how to give an understandable scientific talk.

Duties of Participants
In the initial meeting, students choose a topic to work on and are assigned a tutor. During the seminar, the student has to understand the relevant literature and writes a paper about the chosen topic (~12 pages). In doing this, he/she receives individual support by the tutor. The produced paper is required to conform to the standards of scientific writing. Finally, each student presents his/her work in a talk to the other participants.

It is also the duty of the participants to reserve enough time for performing the seminar. It is the obligation of the participant to start working in time, and to make appointments with their tutors for regular meetings during the semester. In particular, students must present to their tutors

The seminar is coordinated by Rafael Penaloza.

Last modified: Tue Sep 28 17:46:28 CET 2010