Lune

Profiles2022-2026

Maximilian Probst Gutenberg

ETH Zurich

15Papers
6Last author
18Unique co-authors
1First author
0Solo

First and last author come from byline position, which some venues assign alphabetically.

Recent papers15

  1. A Simple and Fast Reduction from Gomory-Hu Trees to Polylog MaxflowsAuthor 1 of 5SODA 2026
  2. Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update TimeAuthor 3 of 3SODA 2026
  3. Expander Pruning with Polylogarithmic Worst-Case Recourse and Update TimeAuthor 3 of 4SODA 2026
  4. Deterministic Almost-Linear-Time Gomory-Hu TreesAuthor 6 of 9FOCS 2025 · 10 citations
  5. Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-OptimalAuthor 4 of 5SODA 2025 · 3 citations
  6. Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious RoutingsAuthor 3 of 4FOCS 2025 · 1 citation
  7. Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost FlowAuthor 6 of 6STOC 2024 · 11 citations
  8. Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update TimeAuthor 7 of 9SODA 2024 · 3 citations
  9. A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their ApplicationsAuthor 4 of 4STOC 2024 · 2 citations
  10. Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via DualityAuthor 7 of 8FOCS 2024 · 1 citation
  11. Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar GraphsAuthor 4 of 4FOCS 2024
  12. A Deterministic Almost-Linear Time Algorithm for Minimum-Cost FlowAuthor 7 of 9FOCS 2023 · 28 citations
  13. Maximum Flow and Minimum-Cost Flow in Almost-Linear TimeAuthor 6 of 7FOCS 2022 · 135 citations
  14. Derandomizing Directed Random Walks in Almost-Linear TimeAuthor 4 of 4FOCS 2022 · 5 citations
  15. Incremental SSSP for Sparse Digraphs Beyond the Hopset BarrierAuthor 4 of 4SODA 2022 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines