Embedded Files
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 also fortunate to be hosted by Virginia Vassilevska Williams at MIT for a research semester (sponsored by a STIBO Fonden It-Rejsestipendium).
I was awarded for my research with the Frontiers of Science Award 2023, an FOCS Best Paper Award in 2022, and an ESA Best Student Paper Award in 2018. Erica Klarreich has written an excellent article on a breakthrough result for computing maximum flows that I co-authored with Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, and Sushant Sachdeva. Another great read on the same result that goes into much more detail is the following article by Nikhil Srivastava. Finally, I wrote a popular science article about it myself for the magazine 'Spektrum der Wissenschaft' which is available here (but unfortunately behind a paywall).
Interests: My research focuses on developing provably fast algorithms for fundamental graph problems. A particular focus is the development of fast - and ultimately practical - algorithms to compute network flows of all kinds. Network flows are essential to graph algorithms and are used to model complex transportation and routing problems, electric networks, and machine-learning problems and arise as important subproblems in many other graph problems.
Contact: You can reach me via maximilian.probst[at]inf.ethz.ch.
Teaching: I am currently teaching the courses:
Advanced Graph Algorithms and Optimization (with Rasmus Kyng), and
Advanced Graph Algorithms and Optimization Seminar (with Rasmus Kyng), and
Advanced Algorithms (with Johannes Lengler and Bernhard Haeupler)
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.
Ph.D. Advising: I am fortunate to (informally) advise the following Ph.D. candidates:
Simon Meierhans, 2021-present
Aurelio Sulser, 2023-present
Wuwei Yuan, 2024-present
Weixuan Yuan, 2025-present
PhD/ Postdoc Openings/ Project and Thesis Supervision/ Internship Opportunities: I am part of Rasmus Kyng's group at ETH Zurich and if you are interested in working with me and/or our group, it is best to use the resources on https://rasmuskyng.com/ to apply.
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 Digital Health Researcher. We have a son (3Y) and a daughter (1Y).
Pronouns: he/his.
Publications:
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.
2025
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time, with Simon Meierhans and Thatchaphol Saranurak, [arXiv]
Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ1-Oblivious Routings, with Rasmus Kyng and Tim Rieder, FOCS 2025
Deterministic Almost-Linear-Time Gomory-Hu Trees, Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Wuwei Yuan, Weixuan Yuan, FOCS 2025
A Simple and Near-Optimal Algorithm for Directed Expander Decompositions, with Aurelio Sulser, ICALP 2025, [arXiv]
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal, with Daoyuan Chen, Simon Meierhans, and Thatchaphol Saranurak, SODA 2025, [arXiv]
2024
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality, with Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, and Sushant Sachdeva, FOCS 2024, [arXiv]
Near-Optimal (1+ϵ)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs, with Arnold Filtser, Gramoz Goranci and Neel Patel, FOCS 2024, [proceedings]
Practical Expander Decomposition, with Lars Gottesbüren and Nikos Parotsidis, ESA (Track B), [proceedings]
Optimal Electrical Oblivious Routing on Expanders, with Cella Florescu, Rasmus Kyng and Sushant Sachdeva, ICALP 2024, [proceedings], [arXiv]
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Maximum & Minimum-Cost Flow, with Li Chen, Rasmus Kyng, Yang P. Liu and Simon Meierhans, STOC 2024, [proceedings], [arXiv]
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications, with Rasmus Kyng, Simon Meierhans, STOC 2024, [proceedings], [arXiv]
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time, with Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Sushant Sachdeva, Aaron Sidford, SODA 2024, [proceedings], [arXiv]
2023
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow, with Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Sushant Sachdeva, Aaron Sidford, FOCS 2023, [proceedings], [arXiv]
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch, with Sebastian Forster, and Yasamin Nazari, STOC 2023 [proceedings], [arXiv]
Maintaining Expander Decompositions via Sparse Cuts, with Yiding Hua, Rasmus Kyng, and Zihang Wu, SODA 2023, [proceedings], [arXiv]
A Simple Framework for Finding Balanced Sparse Cuts via APSP, with Li Chen, Rasmus Kyng, and Sushant Sachdeva, SOSA 2023, [proceedings], [arXiv]
2022
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time, with Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, and Sushant Sachdeva, FOCS 2022 (Best Paper), [quanta article by Erica Klarreich], [ETH news by Florian Meyer], [CACM article], [ETH D-INFK news], [technical perspective by Shang-Hua Teng], [arXiv], [proceedings], [JACM article]
Derandomizing Directed Random Walks in Almost-Linear Time, with Rasmus Kyng and Simon Meierhans, FOCS 2022, [proceedings], [arXiv]
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary, with Aaron Bernstein, Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun, ICALP 2022 [arXiv], [proceedings]
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets, with Ming Ding, Rasmus Kyng and Peng Zhang, ICALP 2022 [arXiv], [proceedings]
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier, with Rasmus Kyng and Simon Meierhans, SODA'2022, [proceedings], [arXiv]
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs, with Debarati Das and Christian Wulff-Nilsen, SODA'2022, [proceedings]
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs, with Debarati Das, Evangelos Kipouridis and Christian Wulff-Nilsen, SOSA'2022, [proceedings], [arXiv]
2021
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time, with Aaron Bernstein and Thatchaphol Saranurak, FOCS'2021, [proceedings], [arXiv], [Talk by Aaron @Dimap] [Talk by Thatchaphol]
Decremental APSP in Directed Graphs Versus an Adaptive Adversary, with Jacob Evald, Viktor Fredslund-Hansen and Christian Wulff-Nilsen, ICALP'2021, [proceedings], [arXiv]
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners, with Thiago Bergamaschi, Monika Henzinger, Virginia Vassilevska Williams and Nicole Wein, SODA'2021, [proceedings], [arXiv]
2020
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing, with Aaron Bernstein and Thatchaphol Saranurak, FOCS'2020, [arXiv], [Talk @FOCS'2020]
Near-Optimal Decremental SSSP in Dense Weighted Digraphs, with Aaron Bernstein and Christian Wulff-Nilsen, FOCS'2020, [arXiv], [Talk by Christian @FOCS'2020], [Article in a Danish Newspaper]
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs, with Virginia Vassilevska Williams and Nicole Wein, STOC'2020, [proceedings], [arXiv], [Talk by Nicole @STOC]
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary, with Christian Wulff-Nilsen, SODA'2020, [proceedings], [arXiv], [Lecture by Christian]
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler, with Christian Wulff-Nilsen, SODA'2020, [proceedings], [arXiv]
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds, with Christian Wulff-Nilsen, SODA'2020, [proceedings] [arXiv] [Lecture by Christian]
2019
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time, with Aaron Bernstein and Christian Wulff-Nilsen, STOC'2019, Invited to SICOMP special issue 2022, [journal], [proceedings], [arXiv]
2018
On the complexity of the (approximate) nearest colored node problem, ESA'2018 (Best Student Paper (Track A)), [proceedings], [arXiv]
Thesis:
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.
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs, [arXiv]
Recent & Upcoming talks:
Talk @University of Salzburg: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time, 15. March 2022
Talk @University of Washington: Faster Flow Algorithms via Dynamic Graph Data Structures, 22. February 2022
Talk @FOCS'2021: Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time, 10. February 2022
Invited Talk @Northerwestern Junior Theorists Workshop: Faster Flow Algorithms via Dynamic Graph Data Structures, 9. December 2021 [slides]
Talk @University of Salzburg: Near-Optimal Decremental SSSP in Dense Weighted Digraphs, 10. November 2021
Ph.D. Defense @KU in CPH: Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs, December 2020 [slides]
Talk @ETH seminar: Directed Expander Decomposition and Congestion Balancing with Applications, November 2020 [talk] [slides]
Talk @FOCS: Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing, November 2020 [talk], [slides]
Talks @BIU (Bar-Ilan University) and @BARC (University of Copenhagen): Near-Optimal Decremental SSSP in Dense Weighted Digraphs, May 2020 [slides]
2 Talks @SODA'20: Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler [slides] and Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds [slides].
Talk @ALU (Alberts-Ludwigs-University Freiburg) and @KTH (Royal Institute of Technology Stockholm): Towards Optimal Algorithms for Decremental Strongly-Connected Components and Single-Source Shortest Paths in Directed Graphs, November/ December 2019 [slides]
Talk @STOC'19: Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time, June 2019, [slides]
A&C talk @MIT: Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time, March 2019, [slides]
Talk @ESA'18: On the complexity of the (approximate) nearest colored node problem, August 2018, [slides]
A&C Seminar @ETH Zurich
I am currently the organizer of the A&C seminar at ETH Zurich (with a lot of help from Ming Ding). Visit the webpage for exciting upcoming talks and to find recordings of talks from the past.
Academic Service:
Program Committee for SODA 2025, SOSA 2025, ESA (Track S) 2024, ESA (Track A) 2023, STOC 2021
Interviewee for Quanta (see the following fantastic article by Ben Brubaker)
Reviewer for all major conferences in the field (i.e. STOC, FOCS, SODA, ICALP, and ESA)
Teaching (detailed):
@ETH: I am a co-instructor of the courses
Advanced Graph Algorithms and Optimization 2021, 2022, 2023, 2024, 2025 where I am responsible for creating and teaching roughly one-third of the course content (i.e. lectures, lecture notes, exercises, and graded homework).
Advanced Graph Algorithms and Optimization Seminar 2021, 2022, 2023, 2024 where I am selecting topics for students to present with Rasmus Kyng, and help to run the seminar.
Advanced Algorithms 2023, 2024 where I am responsible for lecturing and administrating roughly one-third of the course content.
@University of Copenhagen: I gave guest lectures in the following courses:
"Randomized Algorithms", 2018/19
"Topics in Algorithms and Data Structures", 2018/19
"Randomized Algorithms for Data Analysis", 2020
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).
Project Supervision:
Master Thesis and Projects
Lennart Küssner (joint with Tianyi Zhang)
Levin Bussat (joint with Simon Meierhans)
Tim Rieder (joint with Rasmus Kyng)
Ilya Maier (joint with Rasmus Kyng)
Elia Haemmerli (joint with Rasmus Kyng)
Daoyuan Chen (joint with Simon Meierhans)
Aurelio Sulser (joint with Simon Meierhans), now Ph.D. student with Rasmus Kyng at ETH Zurich (informally co-advised by me)
Simon Meierhans (joint with Rasmus Kyng), winner of the ETH Silver Medal that honors outstanding Master theses, now Ph.D. student with Rasmus Kyng at ETH Zurich (informally co-advised by me)
Zihang Wu (joint with Rasmus Kyng), now Ph.D. student at Max-Planck Institute Saarbrücken
Yiding Hua (joint with Rasmus Kyng), now Ph.D. student at ETH Zurich
Charlotte Out (joint with Rasmus Kyng), now Ph.D. student at the University of Cambridge
Mathias Mortensen (joint with Mikkel Thorup)
Google Sites
Report abuse