Some algorithms that solve NP-hard problems become 1000x faster by incorporating a preprocessing step that simplifies the input before solving it. Why, how, and when does this work? We offer a postdoc position in the ReduceSearch project, which aims to understand and expand the power of preprocessing.

TU Eindhoven is offering a 1-year postdoc position for a talented and motivated researcher with a strong interest in algorithms and complexity. The research is supported by ERC Starting grant "Rigorous Search Space Reduction" and is aimed at advancing the theory of algorithmic preprocessing. The project investigates questions such as: why does preprocessing lead to such large speedups for some NP-hard problems? How does a preprocessing algorithm reduce the search space of the follow-up algorithm? Which aspects of a problem input make it amenable to preprocessing? How can new preprocessing algorithms be developed that deliver speedups of several orders of magnitude? These questions are tackled using the framework of parameterized complexity and kernelization, and are asked for a diverse set of NP-hard problems concerning graphs, logic, and constraint satisfaction.

The position is supervised by dr. Bart M. P. Jansen (https://www.win.tue.nl/~bjansen/ )

The postdoctoral candidate is required to have a strong background in algorithms or computational complexity. Experience within the domain of parameterized complexity, kernelization, or constraint satisfaction problems is a plus. Candidates are expected to be fluent in English, both oral and in writing, and to have obtained a PhD degree.

The postdoctoral candidate will be expected to conduct independent research on topics relevant to the above agenda, to publish this research at conferences and journals, and to cooperate with the PhD candidates and principal investigator of the ReduceSearch project. The position does not have any required teaching duties. If the postdoctoral candidate wishes to further their development by assisting with the daily supervision of master- or PhD students, there will be opportunities to do so.

The starting date is negotiable, but must be no later than January 1st 2023. The position is offered for a period of one year, which may be extended.

• A meaningful job in a dynamic and ambitious university with the possibility to present your work at international conferences.
• A full-time employment for 1 year.
• You will have free access to high-quality training programs on general skills, didactics and topics related to research and valorization.
• A gross monthly salary and benefits in accordance with the Collective Labor Agreement for Dutch Universities.
• Additionally, an annual holiday allowance of 8% of the yearly salary, plus a year-end allowance of 8.3% of the annual salary.
• The position comes with ample travel budget to engage in research activities abroad.
• A broad package of fringe benefits (including an excellent technical infrastructure, moving expenses, and savings schemes).
• Should you come from abroad and comply with certain conditions, you can make use of the so-called '30% facility', which permits you not to pay tax on 30% of your salary.
• Family-friendly initiatives are in place, such as an international spouse program, and excellent on-campus children day care and sports facilities.