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