Postdoc positions are available in algorithms & complexity at Max-Planck-Institut für Informatik, Saarbrücken, Germany, supported by the ERC Consolidator Grant SYSTEMATICGRAPH.
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.
Closest substring problems with small distances.
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
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
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
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
M. Grohe, D. Marx.
SIAM Journal on Computing, 44(1):114-159, 2015. (Conference version
in STOC 2012.)
ERC Starting Grant PARAMTIGHT:
"Parameterized complexity and the search for tight complexity
ERC Consolidator Grant SYSTEMATICGRAPH:
"Systematic mapping of the complexity landscape of hard algorithmic graph
- Former postdocs:
Graduated PhD students: