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]inf.ethz.ch.
Teaching: I am currently teaching the courses:
Advanced Graph Algorithms and Optimization (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.
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.
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 applications-kyng@lists.inf.ethz.ch (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.
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.
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 [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], [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. Visit the webpage for exciting upcoming talks and to find recordings of talks from the past.
Academic Service:
Program Committee for ESA 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 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 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).
Supervision:
Master Thesis and Projects
Aurelio Sulser
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.
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)
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.