PhD Position on Parameterized and Fine-Grained Complexity of NP-Hard Problems

This position focuses on fundamental open problems in algorithm design and computational complexity. The main theme will be a unifying theory of algorithmic power of combinatorial decompositions (such as tree decompositions) and algebraic decompositions (such as matrix-rank–based methods), combining elegant fundamental mathematics with computer science. There is also freedom to explore related topics in Parameterized/Fine-grained complexity or Theoretical Computer Science at large.

Your job
In algorithm design, the paradigm of decomposition is omnipresent. In the 5-year ERC project COALESCE we aim for new fundamental insights on this paradigm, especially in the context of Parameterized Complexity and Fine-grained complexity of NP-hard problems.

As a PhD candidate in the COALESCE project, you will have the opportunity to contribute to cutting-edge research in algorithms and computational complexity. You will:

• Conduct research on fundamental open problems in algorithm design and computational complexity.
• Develop a new theory for combinatorial decompositions (e.g., tree decompositions) and algebraic decompositions (e.g., matrix-rank–based approaches) of search spaces.
• Design and analyse algorithms inspired by these decompositions methods.
• Collaborate with your daily supervisor and other researchers of the COALESCE project team and algorithms and complexity group.
• Present your findings at international conferences and in journal papers.
• Contribute to the scientific community through discussions, reading groups, seminars, and light teaching or supervision tasks.

You will join the Algorithms and Complexity group at Utrecht University with Jesper Nederlof as daily supervisor. The starting date is negotiable, but should not be later than October 2026.

We are looking for a passionate new colleague who meets the following criteria:

• a Master’s degree in Computer Science or Mathematics;
• you have a background in algorithms, computational complexity, or discrete mathematics and demonstrable experience with all three of these areas;
• you aspire to be a tenacious and creative researcher in computer science with great affinity for (mathematical) puzzle-solving;
• demonstrable experience within the domain of parameterized complexity or fine-grained complexity and a strong mathematical background are a plus;
• you are proficient in English, both written and spoken.

• a position for 18 months, with an extension to a total of four years upon successful assessment in the first 18 months;
• a gross monthly salary between € 3.059 and €3.881 in the case of full-time employment (salary scale P under the Collective Labour Agreement for Dutch Universities (CAO NU));
• 8% holiday pay and 8.3% year-end bonus;
• a pension scheme, partially paid parental leave and flexible terms of employment based on the CAO NU.

In addition to the terms of employment laid down in the CAO NU, Utrecht University also offers a range of its own schemes for employees. This includes arrangements for professional development, various types of leave, and options for sports and cultural activities. You can also tailor your employment conditions through our Terms of Employment Options Model. In this way, we encourage you to keep investing in your personal and professional development. For more information, please visit Working at Utrecht University.

A better future for everyone. This ambition motivates our scientists in executing their leading research and inspiring teaching. At Utrecht University, the various disciplines collaborate intensively towards major strategic themes. Our focus is on Dynamics of Youth, Institutions for Open Societies, Life Sciences and Pathways to Sustainability. Sharing science, shaping tomorrow.

Working at the Faculty of Science means bringing together inspiring people across disciplines and with a variety of perspectives and backgrounds. The Faculty has six departments: Biology, Pharmaceutical Sciences, Information & Computing Sciences, Physics, Chemistry and Mathematics. Together, we work on excellent research and inspiring education. We do so, driven by curiosity and supported by outstanding infrastructure. Visit us on LinkedIn and discover how you can become part of our community.

The Department of Information and Computing Sciences has a long and strong tradition in research in the classic field of the design and analysis of algorithms, and the complexity of computational problems. The Algorithms and Complexity (A&C) group that hosts the ERC project of PI Jesper Nederlof includes several renowned researchers in the area of parameterized complexity such as Hans Bodlaender and Erik Jan van Leeuwen. The team funded by the ERC project COALESCE currently consists of one PhD student and one Postdoc and is expected to grow more in the coming years. Additionally, the department has a strong group on geometric computing with tight connections to the A&C group.

For more information, please contact Jesper Nederlof at j.nederlof@uu.nl.

Do you have a question about the application procedure? Please send an email to science.recruitment@uu.nl.