Postdoc Position: ERC SYSTEMATICGRAPH project
Postdoc positions are available at the Algorithms & Complexity group of the Max Planck Institute for Informatics in Saarbrücken, supported by the European Research Council (ERC) Consolidator Grant “SYSTEMATICGRAPH: Systematic mapping of the complexity landscape of hard algorithmic graph problems” held by Dániel Marx.
The Max Planck Institute for Informatics is located on the campus of Saarland University in Saarbrücken, Germany. Our working language is English. The group collaborates with several major research institutions in Europe and the U.S. and has high international visibility. There is generous travel support available for all group members.
The goal of the project is to put the search for tractable algorithmic graph problems into a systematic and methodological framework: instead of focusing on specific sporadic problems, we intend to obtain a unified algorithmic understanding by mapping the entire complexity landscape of a particular problem domain. A dichotomy theorem is a complete classification result that characterizes the complexity of each member of a family of problems: it identifies all the cases that admit efficient algorithms and proves that all the other cases are computationally hard. Achieving such a complete understanding for a family of problems requires the joint effort of algorithm design (to identify all the tractable cases) and computational complexity (to give lower bounds for the hard cases). While dichotomy theorems are common in the context of Constraint Satisfaction problems, there is growing evidence that the theory of algorithmic graph problems have an equally rich set of classification results waiting to be discovered. The framework of parameterized complexity and fixed-parameter tractability seems to be a particularly good source of potential dichotomy theorems, but the search for polynomial-time exact or approximation algorithms can be also done in such an exhaustive manner. The project will demonstrate that complete complexity classifications are feasible for a wide range of graph problems coming from areas such as finding patterns, routing, and survivable network design, and novel algorithmic results and new levels of algorithmic understanding can be achieved even for classic and well-studied problems.
The candidates 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. Strong background parameterized complexity, fixed-parameter tractability, graph theory, combinatorics, or approximation is of advantage.
Electronic applications are mandatory, the submission server is now open and available here. The deadline for applications is November 30, 2019, with a flexible starting date in 2020. Please mention the project SYSTEMATICGRAPH in the Potential collaborators field of the application form.
Please prepare a single PDF file containing:
- a curriculum vitae
- a complete list of publications, and
- a research statement (1 page suffices).
Moreover, you will be asked to provide the names and email addresses of three references, who will be asked to provide letters of references by the application deadline. Please contact dmarx@mpi-inf.mpg.de concerning any questions.