Maximilian Probst Gutenberg

Position: I am an Established Researcher (german "Oberassistant") at ETH Zürich in Rasmus Kyng's group. 

I received my Ph.D. in 2020 at the University of Copenhagen under the great supervision of Christian Wulff-Nilsen and Mikkel Thorup. I was also a part of the Basic Algorithm Research Group Copenhagen (BARC). 

During my Ph.D. studies, I was fortunate to be hosted by Virginia Vassilevska Williams at MIT for a period of 4 months (sponsored by a STIBO Fonden It-Rejsestipendium).

I was awarded for my research with the Frontiers of Science Award 2023, a FOCS Best Paper Award in 2022, and an ESA Best Student Paper Award in 2018.

Interests: I am interested in Graph Algorithms, Optimization, and Data Structures. I have mainly worked on Shortest Paths, Flows & Cuts, Expanders, and Connectivity/ Reachability.

Contact: You can reach me via maximilian.probst[at]

Teaching: I am currently teaching the courses:

At the bottom of this page, you can also find the materials from previous years and info on other courses that I taught and TAed for.

Project and Thesis Supervision: We offer project and thesis supervision for students at ETH Zurich. Please see on how to get in touch. Please note that we cannot offer thesis supervision for non-ETH Zurich students.

Internship Opportunities: Currently, we cannot offer internships of any form.

Ph.D. and Postdoc Applications: If you are interested in applying to a Ph.D. in our group, you can apply to Rasmus Kyng by sending an email to (as a precaution against spam filters, cc me and Rasmus as well). Students accepted are then usually jointly mentored. 

If you would like to start directly after receiving a bachelor's degree, you should apply to our Direct Doctorate Program (joint Master's and Ph.D.), and also send us an email to let us know you are interested in joining our group. Candidates should have a strong background in theoretical computer science or mathematics.

Strong theory researchers interested in doing a postdoc at ETH are highly encouraged to apply to the ITS junior fellowship.

Bibliographic Info: I maintain a profile on Google Scholar and you can find me on DBLP and OrchID to see publication details and citations.

Personal Info: I am married to Johanna Gutenberg who is a researcher in the field of eHealth and ICT.

Pronouns: he/his.


Results in Theoretical Computer Science are often published at conferences. STOC, FOCS, and SODA are the three top conferences in our field according to the CORE Ranking and the Google Scholar Ranking. All results with [arXiv] next to them are openly accessible, by clicking on the underlined text.








During the three years of my Ph.d., I have focussed on obtaining better algorithms for the dynamic Single-Source Shortest Paths (SSSP), Strongly-Connected Components (SCCs) and Single-Source Reachability (SSR) problems. In these problems, we want to maintain SSSP, SCCs or SSR as a (directed) graph undergoes edge deletions. These problems are fundamental primitives in (directed) dynamic graphs, and have important applications for many static graph problems. The thesis below gives some of the highlights of this line of research and puts them into context.

Recent & Upcoming talks:

A&C Seminar @ETH Zurich

I am currently the organizer of the A&C seminar at ETH Zurich. Visit the webpage for exciting upcoming talks and to find recordings of talks from the past.

Academic Service:

Teaching (detailed):

I was a Teaching Assistant in the courses "Advanced Algorithms and Data Structures" (2x), "Randomized Algorithms" @University of Copenhagen, and for "Einsatz von Informatikmitteln” @ETH (2x).


Master Thesis and Projects

If you are a student at ETH Zurich and interested in writing your thesis/ conducting a project, feel free to contact me via e-mail.