Seminar

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

Prerequisites

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

Language

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

• a full version of their paper at least 5 weeks before their talk and
• a first version of all the slides for their talk at least 2 weeks before the talk.

Contact

The seminar is coordinated by Rafael Penaloza.