Bachelor and Master Seminar WS2020
Seminar Kernelization
Contact
Content
Kernelization is the theory of efficient preprocessing algorithms.
When given an instance to a problem, the goal is to reduce the size of the instance as much as possible.
What is then left over is a so-called kernel, which captures the essence of the instance.
For some problems such a kernel can be found and for others (under reasonable assumptions) this is not possible.
There exists a rich set of algorithmic techniques for kernelization
and a well established theory about which problems can and cannot be kernelized.
The goal of this seminar is to make the students familiar with these results.
The seminar will follow this book by Fomin et. al.
The book will be available in the library.
Structure
There will be weekly meetings in which the participants give their talks
Requirements
Participants should have a keen interest in theoretical computer science, but no prior knowledge is kernelization is necessary.
Material
Slides from the kick-off meeting.
Dates
| Date | Topic | Student |
| 13.05.2020 | Inductive Priorities | Jonas Spang |
| 13.05.2020 | Crown Decomposition | Simon Klemp |
| 20.05.2020 | Expansion Lemma | Felix Friedberger, Jana Lemke |
| 27.05.2020 | Linear Programming | Maximilian Sudmann,Konrad Ostrowski |
| 10.06.2020 | Modules | Anna Perret, Niklas Berndt |
| 17.06.2020 | Sunflower Lemma | Maxim Pakhomenko |
| 17.06.2020 | Matroids | Dominic Meiser |
| 24.06.2020 | Greedy Packing | Celina Kalus |
| 24.06.2020 | Euler's Formula | Julian Schnitzler |
| 01.07.2020 | Instance Selectors | Marlene Damm |
| 01.07.2020 | Polynomial Parameter Transformation | Magnus Groß |
| 08.07.2020 | Polynomial Lower Bounds | Mohamad Altalli |
| 08.07.2020 | Turing Kernelization | Sijia Guo |
| 15.07.2020 | Lossy Kernelization | Michael Nguyen |
Essay
Your essay should be in English, written using LaTeX and
should not exceed 8 pages (excluding references). Please use
this template (or something equivalent).
The deadline to hand in your essay is
August 17th at 10:00.
