Maximilian Probst Gutenberg

Position: I am a Post Doc 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).

Interests: I am very 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.

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 in 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 it are openly accessible, by clicking on the underlined text.

2022

  1. 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]

  2. Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets, with Ming Ding, Rasmus Kyng and Peng Zhang, ICALP 2022 [arXiv]

  3. Maintaining Expander Decompositions via Sparse Cuts, with Yiding Hua, Rasmus Kyng, and Zihang Wu, [arXiv]

  4. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time, with Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, and Sushant Sachdeva, [arXiv]

  5. Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier, with Simon Meierhans and Rasmus Kyng, SODA'2022, [proceedings], [arXiv]

  6. A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs, with Debarati Das and Christian Wulff-Nilsen, SODA'2022, [proceedings]

  7. 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

  1. 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]

  2. Decremental APSP in Directed Graphs Versus an Adaptive Adversary, with Jacob Evald, Viktor Fredslund-Hansen and Christian Wulff-Nilsen, ICALP'2021, [proceedings], [arXiv]

  3. 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

  1. 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]

  2. 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]

  3. 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]

  4. Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary, with Christian Wulff-Nilsen, SODA'2020, [proceedings], [arXiv], [Lecture by Christian]

  5. Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler, with Christian Wulff-Nilsen, SODA'2020, [proceedings], [arXiv]

  6. 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

  1. 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

  1. On the complexity of the (approximate) nearest colored node problem, ESA'2018, [proceedings], [arXiv], Best Student Paper (Track A)

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]

Academic Service:

  • Program Committee for STOC 2021

  • I have reviewed articles for all major conferences in the field (i.e. STOC, FOCS, SODA, ICALP, and ESA)

Teaching:

  • @ETH: I am a co-instructor of the course Advanced Graph Algorithms and Optimization where I am responsible for creating and teaching roughly one-third of the course content (i.e. lectures, lecture notes, exercises, and graded homework).

  • @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.

Supervision

Master Thesis and Projects

  • 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)

  • Yiding Hua (joint with Rasmus Kyng)

  • Charlotte Out (joint with Rasmus Kyng)

  • 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.