Send email Copy Email Address

Email

Address

Kaiserstraße 170-174
66386 St. Ingbert (Germany)

Short Bio

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.

CV: Last four stations

2019-2020
Senior researcher - Max Planck Institute for Informatics, Saarbrücken, Germany
2012-2019
Senior research fellow - Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Hungary
2010-2011
Humboldt Research Fellowship for Experienced Researchers - Institut für Informatik, Humboldt-Universität zu Berlin, Germany, Host: Prof. Martin Grohe
2009-2010
Postdoc researcher - Blavatnik School of Computer Science, Tel Aviv University, Israel, Host: Prof. Noga Alon

Publications by Dániel Marx

Year 2021

Year 2020

Conference / Medium

ESA
28th Annual European Symposium on Algorithms (ESA 2020)ESA 2020

Conference / Medium

ESA
28th Annual European Symposium on Algorithms (ESA 2020)ESA 2020

Teaching by Dániel Marx

Winter 2021/22

Parameterized Algorithms

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.

Format

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

Prerequisites

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    

 

Reference Textbook

"Parameterized Algorithms" by Cygan et al. (see this for free pdf of the book from the authors).