TU Dresden
Institut für Theoretische Informatik
Lehrstuhl für Automatentheorie

Hauptseminar "Complexity of enumeration problems" in Summer Term 2007

Initial Meeting

The initial meeting will take place on 4th April, 9:20-10:50, in Room E05. Attending the initial meeting is mandatory for participation in the seminar. People who want to participate in the seminar, but have serious reasons to not attend the initial meeting, please send an email.

Presentations

The presentations will take place in one meeting at the end of the semester (the date and place to be announced). Attending all of the talks is mandatory for all participants

Position in Curriculum

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

Prerequisites

Basic knowledge in complexity theory.

For computer scientists: Pflichtvorlesung Grundlagen der Theoretischen Informatik.

Language

The language of the initial meeting is English .

Topic of the Hauptseminar

Complexity theory traditionally considers decision problems, i.e., problems that have a yes/no answer. In many applications, however, one is not only interested in the existence of a solution, but also in actually obtaining the solutions. If a given problem has instances with exponentially many solutions, then an algorithm enumerating all solutions obviously needs exponential time in the worst case. However, the quality of such exponential enumeration algorithms may still vary considerably. For example, one can ask whether the algorithm has exponential runtime only if there are indeed exponentially many solutions, or how long the delay is between the generation of different solutions.

In the seminar, we will consider different such approaches for analyzing the complexity of enumeration algorithms and their application to enumeration problems in different areas of computer science.

List of papers

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

Hints on how to prepare a paper and how to give a talk are available (in German).

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. The sharp deadline for finishing is the end of the semester. Failure to finish the project in time will result in no credits to be given. It is the obligation of the participant to start working in time, and to make appointments with the supervisor for regular meetings during the semester.

Contact

The seminar is coordinated by Barbara Morawska.