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.
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:
https://www.mpi-inf.mpg.de/departments/algorithms-complexity/offers/SYSTEMATICGRAPH/
(or https://bit.ly/2MKWPvy )
The deadline for applications is November 30, 2019, with a flexible
starting date in 2020.
Please contact dmarx@mpi-inf.mpg.de concerning any questions.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
