and Control (Hungarian Academy of Sciences), Budapest, Hungary,
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 positions are for
one year, with the possibility of renewal.
http://www.cs.bme.hu/~dmarx/job.html
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.
The review of applicants will begin immediately and continue until the
positions are filled. The ideal starting date is March 1, 2018. A
completed PhD degree is an administrative prerequisite for starting the
position. Applications received by November 15, 2017 will receive full
consideration. To apply, send a CV and a research statement by email to
Dániel Marx ( dmarx at cs dot bme dot hu ) and arrange two letters of
recommendation to be send to this address. Questions and informal
inquiries are welcome.
http://www.cs.bme.hu/~dmarx/job.html
**********************************************************
*
* 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
