66386 St. Ingbert (Germany)
Dániel Marx obtained his PhD in 2005 at the Budapest University of Technology and Economics in Hungary. After that, he had postdoc researcher and visiting researcher positions in Berlin, Budapest, and Tel Aviv. From 2012 to 2019, he was at the Institute for Computer Science and Control of the Hungarian Academy of Sciences, where he has founded the Parameterized Algorithms and Complexity group, funded from his European Research Council Starting and Consolidator Grants. In 2019, he became a senior researcher at the Max Planck Institute for Informatics in Saarbrücken, and joined CISPA as a tenured faculty member in 2020. Dániel is known for his theoretical work on algorithms and lower bounds for a wide range of problems.
28th Annual European Symposium on Algorithms (ESA 2020)ESA 2020
This course is about designing fast algorithms for NP-hard graph theoretic problems, where the running time depends on multiple parameters of the input. For example, while a database may contain a very large amount of data, the size of the database queries is typically extremely small in comparison. The aim would be to obtain algorithms that have a small dependence on the database size, but possibly a larger dependence on the query size. Such an algorithm would be fast when the queries are small.
We will see several algorithmic techniques to design fast algorithms for NP-hard problems in this setting, called Fixed Parameter Tractable (FPT) algorithms, as well as an overview of the lower-bound methods. We will also learn about preprocessing or data-reduction algorithms in this setting, called Kernelization algorithms, which run in polynomial time and reduce a given instance of a NP-hard problem to an equivalent but much smaller instance.
Two hours of lectures every week and two hours of tutorials every other week.
Lectures: Tuesday, 10:15-12:00, online over Zoom
First lecture: October 19, 2021
Basic knowledge of algorithms, graph theory and probability will be assumed.
|Date||Topic||Material||Reference (see below)||Exercise||Due|
|October 19||L01: Introduction I||Slides Video||1, 3.1, 3.2, 3.3|