There currently is an open position for a PhD student in the project “Dynamic Algorithms Against Strong Adversaries (DynASoAr)” funded by the ERC Starting Grant of Assistant Professor Sebastian Forster from the Efficient Algorithms Group at the University of Salzburg, Austria (https://www.cs.sbg.ac.at/~forster/). The main goal of this project is to design new dynamic algorithms with theoretical guarantees for fundamental graph problems.

* Requirements: Master’s degree in computer science, informatics, or mathematics and generally a strong interest in algorithms, theoretical computer science, or graph theory
* Start date: Fall 2021 (September – November), negotiable
* Duration: Three years with the possibility of extension by another year
* Salary: 41.601 EUR gross/year for 40 hours/week
* Application deadline: April 25, 2021. Late applications will be considered until the position is filled.

To apply for this position, please send your CV, a short letter of motivation explaining your academic background, the (tentative) abstract of your Master’s thesis, and a transcript of your courses and grades to forster@cs.sbg.ac.at. Please include the words “application” or “PhD” in the subject line. The same email address can be used to send informal inquiries as well.

About the project: The main goal of this project is to design new algorithms for dynamic graphs. In many cases, such as social networks or road networks, algorithms need to run on dynamically evolving graphs. To be precise, the algorithm should react quickly to edge insertions and deletions in the graph. The problems being studied are fundamental in nature, including, but not limited to, shortest path, maximal matching, minimum cut, maximum flow, spanners, and sparsifiers. Depending on the interests of the applicant, it is also possible to work on the computational complexity of these problems and try for hardness results.