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, 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.
Interests: I am interested in Graph Algorithms, Optimization, and Data Structures. I have mainly worked on Flows & Cuts, Shortest Paths, Expanders, and Connectivity/ Reachability.
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, 2022-present
Aurelio Sulser, 2023-present
PhD Openings: If you're interested in applying to do a PhD in our group, you can send an email to applications-kyng@lists.inf.ethz.ch (as a precaution against spam filters, cc Rasmus and me as well). Please include your transcript, a CV, and any other relevant information. We may request letters of recommendation later in our interview process, but prefer to receive these directly from recommenders.
Our standard PhD program requires you to hold a master's degree when you start. 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 PhD), and also send an email to the above address to let me know you are interested in joining my group. Candidates should have a strong background in theoretical computer science or mathematics.
Students in our group are usually jointly mentored by Rasmus Kyng and myself.
Postdoc Openings: We have an opening for a two-year postdoc in our group. Candidates should have a strong publication record in theoretical computer science and research interests that overlap with our group. The starting date is flexible, and we offer a competitive salary, and generous funding for work travel.
To apply, send an email to applications-kyng@lists.inf.ethz.ch (as a precaution against spam filters, cc Rasmus and me as well). Please include your CV and any other relevant information. We may request letters of recommendation later in our interview process, but prefer to receive these directly from recommenders. Beyond the postdoc positions in our group, theory researchers interested in doing a postdoc at ETH are also highly encouraged to apply to the ITS junior fellowship
Project and Thesis Supervision: We offer project and thesis supervision for students at ETH Zurich. Please see https://kyng.inf.ethz.ch/supervision/ 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.
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 (1Y) and a daughter (0Y).
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.
2024
A Simple and Near-Optimal Algorithm for Directed Expander Decompositions, with Aurelio Sulser, [arXiv]
Optimal Electrical Oblivious Routing on Expanders, with Cella Florescu, Rasmus Kyng and Sushant Sachdeva, ICALP 2024
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, [arXiv]
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications, with Rasmus Kyng, Simon Meierhans, STOC 2024, [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], [CACM article], [ETH D-INFK news], [technical perspective by Shang-Hua Teng], [arXiv], [proceedings]
Derandomizing Directed Random Walks in Almost-Linear Time, with Rasmus Kyng and Simon Meierhans, FOCS 2022, [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 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 where I am selecting topics for students to present with Rasmus Kyng, and help to run the seminar.
Advanced Algorithms 2023 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
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)