This course is taught in English. This seminar was last offered in Winter Term 2020/21.
Parameterized Complexity aims to rene the traditional notion of NP-hardness by providing reasons as to why certain problems are (probably) hard to solve. It does this by analyzing algorithm performance not just depending on the instance size, but on additional parameters of the problem such as the size of the desired solution. This often allows us to design algorithms that have runtimes polynomial in the instance size, and super-polynomial in the observed parameters, showing that the hardness of the problem stems not from the size of the instance but from the size of the parameter. Such a rened notion of complexity has driven the developement of a large collection of theoretical breakthroughs and novel algorithmic techniques. Withing this seminar we aim to give an accessible overview of the most prominent of these results and their applications in designing state-of-the-art algorithms.
We are looking for students with an interest in theoretical computer science and algorithm design. Some of the topics to be discussed are fairly technical and experience with graph theory, algorithm analysis, probability theory, and complexity theory will be benecial. However, the range of topics is quite wide, so a lack of background in some of these topics should not be an obstacle. The seminar is open to bachelor students in CS, DS, IIW, and TM.
The seminar will cover up to 10 topics, depending on the number of participants. Each topic will be covered by one student, who will work through a paper or problem, give a 30 min presentation on it and write a 1-2 page summary.
There will be 4 sessions in total. First a meeting to discuss and assign topics, then 2 gatherings after 3 weeks respectively and one nal day on which all presentations will be held. We're targeting at most 10 participants. The exact dates are still to be determined.
The following is a selection of potential topics to be covered in the seminar: