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.

Current group members:

• Jacob Focke, postdoc
• Esther Galby, postdoc
• Ariel Kulik, postdoc
• Fionn Mc Inerney, postdoc
• Daniel Neuen, postdoc
• Prafullkumar Tale, postdoc
• Philipp Schepper, PhD student

CISPA Helmholtz Center for Information Security (Saarbrücken, Germany) offers several 2-year postdoc positions in the Algorithms & Complexity group of Dániel Marx.

Currently we are hiring in ALL topics related to algorithms & complexity!

CISPA is a German national Big Science Institution within the Helmholtz Association. The working language of the institute is English. The positions are offered with an employment contract and come with social security and generous travel support. There are no teaching obligations associated with the positions. The starting date is flexible.

Strong candidates are sought in ALL theoretical areas related to algorithms and complexity, with particular focus on the following topics:

• graph algorithms
• combinatorial optimization
• parameterized algorithms and complexity

The candidates for the postdoc positions should have (or expect to have shortly) a PhD degree in Computer Science or related area; research experience at postdoctoral level is of advantage. A successful candidate should have excellent knowledge of algorithms and/or complexity with a strong track record of published papers.

Applications for the positions should be submitted online on the CISPA website by September 5, 2021 for full consideration. The uploaded cover letter should

• indicate that the application is to the group of Dániel Marx, and
• provide names and addresses of 3 references.

Informal inquiries are welcome and may be sent to Dániel Marx.

• List of publications (with online papers)
• DBLP
• Google Scholar
• Talks & Slides

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.)
• Parameterized Intractability of Even Set and Shortest Vector Problem.
  A. Bhattacharyya, É. Bonnet, L. Egri, S. Ghoshal, Karthik C. S., B. Lin, P. Manurangsi, D. Marx. Journal of the ACM, 68(3): 16:1-16:40, 2021
• Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.
  V. Cohen-Addad, É. Colin De Verdière, D. Marx, A. De Mesmay. Journal of the ACM, 68(4): 30:1-30:26, 2021

• 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"

See full CV here.

• Former postdocs:

  Akanksha Agrawal É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

• 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