The main focus of my research is reaching the ultimate limits of algorithmic techniques for solving hard computational problems. I am equally interested in working on problems of algorithm design and in using computational complexity to discover the fundamental limitations of efficient algorithms. A large part of my work uses the framework of parameterized complexity to obtain a more fine-grained understanding of problem complexity. I have worked on a wide range of combinatorial problems coming from algorithmic graph theory, combinatorial optimization, constraint satisfaction problems (CSP), and other areas.

Selected publications:

• Closest substring problems with small distances.
  D. Marx. SIAM Journal on Computing, 38(4):1382-1410, 2008. (Conference version in FOCS 2005.)
• Approximation schemes for Steiner Forest on planar graphs and graphs of bounded treewidth.
  M. Bateni, M. Hajiaghayi. D. Marx. Journal of the ACM, 58(5):21, 2011. (Conference version in STOC 2010.)
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries.
  D. Marx. Journal of the ACM, 60(6):42, 2013. (Conference version in STOC 2010.)
• The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable.
  M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 197-206, 2013.
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs.
  M. Grohe, D. Marx. SIAM Journal on Computing, 44(1):114-159, 2015. (Conference version in STOC 2012.)

All publications, DBLP, Google Scholar, Talks & Slides

ERC Starting Grant PARAMTIGHT: "Parameterized complexity and the search for tight complexity results"

ERC Consolidator Grant SYSTEMATICGRAPH: "Systematic mapping of the complexity landscape of hard algorithmic graph problems"

Tutorials:

• Fine-Grained Complexity and Algorithm Design Boot Camp (Simons Institute 2015)
  Videos – Talk 1 – Talk 2 – Talk 3 – Talk 4
• School on Parameterized Algorithms and Complexity (August 2014, Będlewo, Poland)
• Algorithmic Graph Structure Theory (ADFOCS 2013 tutorial slides)
  
• Algorithmic Graph Structure Theory (STACS 2013 tutorial slides)
  
• Open lectures for PhD students in computer science (University of Warsaw 2009):
  Part 1: Algorithmic techniques – Part 2: Treewidth – Part 3: Complexity

Current postdocs:

Akanksha Agrawal

Former postdocs:

Édouard Bonnet, Nick Brettell, Yixin Cao, Lin Chen, Radu Curticapean, László Egri, Andreas Feldmann, Sylvain Guillemot, O-joung Kwon Till Miltzow, Valia Mitsou, Sandeep R.B. Pawel Rzazewski,

Graduated PhD students:

Ildikó Schlotter

Coauthors of my published papers:

Noga Alon, Saeed Akhoondian Amiri, Albert Atserias, Gábor Bacsó, MohammadHossein Bateni, Hans L. Bodlaender, Édouard Bonnet, Nick Brettell, Andrei Bulatov, Sergio Cabello, Yixin Cao, Chandra Checkuri, Hubie Chen, Lin Chen, Rajesh Chitnis, David Cohen, Tibor Cinkler, Martin Cooper, Páidí Creed, Radu Curticapean, Marek Cygan, Víctor Dalmau, Mark de Berg, Holger Dell, Erik Demaine, László Egri, Alina R. Ene, Andreas Feldmann, Dániel Fogaras, Fedor V. Fomin, Panos Giannopoulos, Martin Green, Martin Grohe, Sylvain Guillemot, MohammadTaghi Hajiaghayi, Emmanuel Hebrard, Pinar Heggernes, Pim van 't Hof, Thore Husfeldt, Bart M.P. Jansen, Klaus Jansen, Naonori Kakimura, Ken-ichi Kawarabayashi, Sándor Kisfaludi-Bak, Philip N. Klein, Rolf Klein, Christian Knauer, Nitish Korula, Stefan Kratsch, Stephan Kreutzer, Andrei Krokhin, Martin Kutz, O-joung Kwon, Claus Popp Larsen, Shaohua Li, Daniel Lokshtanov, Neeldhara Misra, Tillmann Miltzow, Valia Mitsou, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Barry O'Sullivan, Marcin Pilipczuk, Michal Pilipczuk, Roman Rabinovich, Igor Razgon, Günter Rote, Pawel Rzazewski András Z. Salamon, Ario Salmasi, Saket Saurabh, Marcus Schaefer, Ildikó Schlotter, Paul Seymour, Anastasios Sidiropoulos, Zsolt Tuza, Tom C. van der Zanden, Erik Jan van Leeuwen, László A. Végh, Nina Taslaman, Yngve Villanger, Martin Wahlén, Magnus Wahlström, Paul Wollan, Deshi Ye, Guochuan Zhang.