JOB DESCRIPTION

The successful candidate will conduct research into the application of kernelization to problems arising in the study of evolutionary trees. The project is primarily algorithmic-theoretical. Knowledge of biology or phylogenetics (which is the study of evolutionary trees) is not required.

Expressed simply, different methods for the inference of evolutionary trees often produce trees with conflicting topologies and we wish to rigorously quantify how dissimilar the trees truly are. A number of dissimilarity measures in the literature are computationally difficult (NP-hard) to compute and we wish to make computation of such distances easier. One approach is to systematically reduce the trees in size without damaging the information within them, in such a way that we can analytically derive bounds on the size of the reduced instances. This technique is called kernelization, which belongs to the wider field of parameterized complexity.

Recent research has shown that there is still much untapped potential for kernelization in the computation of phylogenetic dissimilarity measures. The primary goal of this project is therefore to develop deeper, more aggressive reduction rules, and to explore the theoretical limits of this technique: just how small can we make such trees? There is a primary focus on the much-studied (unrooted) maximum agreement forest problem.  The successful candidate will also research branching algorithms, exponential-time algorithms and polynomial-time approximation algorithms, but kernelization is the main focus of this project.

The project, which is funded by the NWO KLEIN 1 grant “Deep kernelization for phylogenetic discordance”, will be embedded in the Algorithms, Complexity and Optimization (ALGOPT) group at Maastricht University’s Department of Data Science and Knowledge Engineering. Research within ALGOPT focuses on developing and analyzing algorithms with rigorous and verifiable performance guarantees. There is a strong focus on the design and analysis of exact, parameterized, approximation, online and randomized algorithms.

The full-time position is offered for a duration of four years, with yearly evaluations.

REQUIREMENTS

1. A master’s degree (completed, or to be completed shortly) in computer science, (applied) mathematics, operations research or a closely related field;

2. Affinity with algorithm design / combinatorial optimization. Prior knowledge of kernelization (or more generally, parameterized complexity) is a bonus but not essential;

3. Experience with writing mathematical proofs;

4. Programming skills are a bonus, but are by no means essential;

5. Excellent English language skills;

6. Good presentation, communication and organization skills.

為防止簡歷投遞丟失請抄送一份至：boshijob@126.com（郵件標題格式：應聘職位名稱+姓名+學歷+專業+中國博士人才網）