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.

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.

Fixed-term contract: A PhD appointment lasts four years (first year + three years after receiving a positive evaluation).

The salary will be set in PhD salary scale of the Collective Labour Agreement of the Dutch Universities (€2.395 gross per month in first year to €3.061 in the fourth and final year). On top of this, there is an 8% holiday and an 8.3% year-end allowance. The terms of employment of Maastricht University are set out in the Collective Labour Agreement of Dutch Universities (CAO). Furthermore, local UM provisions also apply. Non-Dutch applicants could be eligible for a favorable tax treatment (30% rule).

Maastricht University. Maastricht University (UM) has around 18,000 students and 4,400 employees. Reflecting the university's strong international profile, a fair amount of both students and staff are from abroad. Research at UM is characterized by a multidisciplinary and thematic approach, and is concentrated in research institutes and schools. UM is renowned for its unique, innovative, problem-based learning system, which is characterized by a small-scale and student-oriented approach. UM placed #10 in Times Higher Education’s (THE) Young Universities Ranking 2019, and #127 in THE’s World University Rankings 2020.

http://www.maastrichtuniversity.nl

The Department of Data Science and Knowledge Engineering. Founded in 1992, we are a fast-growing department undertaking internationally respected research in the areas of computer science, human-machine interaction, artificial intelligence and applied mathematics. Much of our research takes place at the interfaces of these disciplines. We maintain a large network of industry partners and provide education through one bachelor’s programme and two master’s programmes, all of which are nationally ranked #1 in their cohort according to the most recent education rankings.

Situated in the heart of Europe and within 30 kilometers from the German and Belgian borders, Maastricht and its 120,000 inhabitants have a strong international character. It is a safe, vibrant city with a history spanning more than 2,000 years. The city’s rich past is reflected everywhere in the streets: the ratio of monuments-to-inhabitants is roughly 1:73. If you are unfamiliar with the Netherlands, UM’s Knowledge Centre for International Staff will gladly assist you with practical.

Our new colleague(s) will be joining a tight-knit department consisting of ~50 principal investigators, postdocs and PhD students, >750 BSc and MSc students and a team of 15 dedicated support staff members. Together, we come from over 40 different countries.

https://www.maastrichtuniversity.nl/dke

STEM research in Maastricht. DKE is embedded in the equally thriving Faculty of Science and Engineering. It’s exciting times for STEM research in the region of Zuid-Limburg, where Maastricht University (UM) is situated. For example, UM recently joined the Einstein Telescope Partnership coalition, which will bring STEM challenges to our doorstep through construction of the ET Pathfinder prototype in the near future. Furthermore, Zuid-Limburg is a hub for the high-tech industry. Maastricht University participates in the four regional Brightlands campuses: local tech ecosystems where fundamental and applied research, state-of-the-art facilities, industry partners and students meet. In addition, the university itself offers no shortage of inspiring collaborators through our international network and the five other faculties of UM.

https://www.maastrichtuniversity.nl/fse