Maximilian Probst Gutenberg

According to our database, Maximilian Probst Gutenberg authored at least 36 papers between 2018 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal.

Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

A Simple and Near-Optimal Algorithm for Directed Expander Decompositions.

Aurelio L. Sulser, Maximilian Probst Gutenberg

CoRR, 2024

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications.

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow.

Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Optimal Electrical Oblivious Routing on Expanders.

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs.

Arnold Filtser, Gramoz Goranci, Neel Patel, Maximilian Probst Gutenberg

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality.

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Practical Expander Decomposition.

Lars Gottesbüren, Nikos Parotsidis, Maximilian Probst Gutenberg

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow.

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Commun. ACM, December, 2023

Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch.

Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Simple Framework for Finding Balanced Sparse Cuts via APSP.

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Maintaining Expander Decompositions via Sparse Cuts.

Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.

Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Webis-MS-MARCO-Anchor-Texts-22.

Maik Fröbe, Sebastian Günther, Maximilian Probst, Martin Potthast, Matthias Hagen

Dataset, January, 2022

A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs.

Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier.

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs.

Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets.

Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.

Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Derandomizing Directed Random Walks in Almost-Linear Time.

Rasmus Kyng, Simon Meierhans, Maximilian Probst

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

The Power of Anchor Text in the Neural Retrieval Era.

Maik Fröbe, Sebastian Günther, Maximilian Probst, Martin Potthast, Matthias Hagen

Proceedings of the Advances in Information Retrieval, 2022

2021

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners.

Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary.

Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.

Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs.

Maximilian Probst Gutenberg

CoRR, 2020

Decremental APSP in Directed Graphs Versus an Adaptive Adversary.

Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

CoRR, 2020

New algorithms and hardness for incremental single-source shortest paths in directed graphs.

Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds.

Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary.

Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler.

Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Near-Optimal Decremental SSSP in Dense Weighted Digraphs.

Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.

Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time.

Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

SIAM J. Comput., 2019

2018

On the Complexity of the (Approximate) Nearest Colored Node Problem.

Maximilian Probst

Proceedings of the 26th Annual European Symposium on Algorithms, 2018