4 Search Results for "Gutenberg, Maximilian Probst"

Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.2
An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk)

Authors: Rasmus Kyng

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In this talk, I will explain a new algorithm for computing exact maximum and minimum-cost flows in almost-linear time, settling the time complexity of these basic graph problems up to subpolynomial factors. Our algorithm uses a novel interior point method that builds the optimal flow as a sequence of approximate minimum-ratio cycles, each of which is computed and processed very efficiently using a new dynamic data structure. By well-known reductions, our result implies almost-linear time algorithms for several problems including bipartite matching, optimal transport, and undirected vertex connectivity. Our framework also extends to minimizing general edge-separable convex functions to high accuracy, yielding the first almost-linear time algorithms for many other problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and isotonic regression. This talk is based on joint work with Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva [Chen et al., 2022]. Our result appeared in FOCS'22 and won the FOCS best paper award.
Cite as

Rasmus Kyng. An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kyng:LIPIcs.ICALP.2023.2,
  author =	{Kyng, Rasmus},
  title =	{{An Almost-Linear Time Algorithm for Maximum Flow and More}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.2},
  URN =		{urn:nbn:de:0030-drops-180543},
  doi =		{10.4230/LIPIcs.ICALP.2023.2},
  annote =	{Keywords: Maximum flow, Minimum cost flow, Data structures, Interior point methods, Convex optimization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.20
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

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

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Designing efficient dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms and has witnessed many exciting recent developments in, e.g., dynamic matching (Wajc STOC'20) and decremental shortest paths (Chuzhoy and Khanna STOC'19). Compared to other graph primitives (e.g. spanning trees and matchings), designing such algorithms for graph spanners and (more broadly) graph sparsifiers poses a unique challenge since there is no fast deterministic algorithm known for static computation and the lack of a way to adjust the output slowly (known as "small recourse/replacements"). This paper presents the first non-trivial efficient adaptive algorithms for maintaining many sparsifiers against an adaptive adversary. Specifically, we present algorithms that maintain 1) a polylog(n)-spanner of size Õ(n) in polylog(n) amortized update time, 2) an O(k)-approximate cut sparsifier of size Õ(n) in Õ(n^{1/k}) amortized update time, and 3) a polylog(n)-approximate spectral sparsifier in polylog(n) amortized update time. Our bounds are the first non-trivial ones even when only the recourse is concerned. Our results hold even against a stronger adversary, who can access the random bits previously used by the algorithms and the amortized update time of all algorithms can be made worst-case by paying sub-polynomial factors. Our spanner result resolves an open question by Ahmed et al. (2019) and our results and techniques imply additional improvements over existing results, including (i) answering open questions about decremental single-source shortest paths by Chuzhoy and Khanna (STOC'19) and Gutenberg and Wulff-Nilsen (SODA'20), implying a nearly-quadratic time algorithm for approximating minimum-cost unit-capacity flow and (ii) de-amortizing a result of Abraham et al. (FOCS'16) for dynamic spectral sparsifiers. Our results are based on two novel techniques. The first technique is a generic black-box reduction that allows us to assume that the graph is initially an expander with almost uniform-degree and, more importantly, stays as an almost uniform-degree expander while undergoing only edge deletions. The second technique is called proactive resampling: here we constantly re-sample parts of the input graph so that, independent of an adversary’s computational power, a desired structure of the underlying graph can be always maintained. Despite its simplicity, the analysis of this sampling scheme is far from trivial, because the adversary can potentially create dependencies between the random choices used by the algorithm. We believe these two techniques could be useful for developing other adaptive algorithms.
Cite as

Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 20:1-20:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bernstein_et_al:LIPIcs.ICALP.2022.20,
  author =	{Bernstein, Aaron and van den Brand, Jan and Probst Gutenberg, Maximilian and Nanongkai, Danupon and Saranurak, Thatchaphol and Sidford, Aaron and Sun, He},
  title =	{{Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.20},
  URN =		{urn:nbn:de:0030-drops-163611},
  doi =		{10.4230/LIPIcs.ICALP.2022.20},
  annote =	{Keywords: dynamic graph algorithm, adaptive adversary, spanner, sparsifier}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.53
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets

Authors: Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, and Peng Zhang

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study linear equations in combinatorial Laplacians of k-dimensional simplicial complexes (k-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacians play a crucial role in homology and are a central tool in topology. Beyond this, they have various applications in data analysis and physical modeling problems. It is known that nearly-linear time solvers exist for graph Laplacians. However, nearly-linear time solvers for combinatorial Laplacians are only known for restricted classes of complexes. This paper shows that linear equations in combinatorial Laplacians of 2-complexes are as hard to solve as general linear equations. More precisely, for any constant c ≥ 1, if we can solve linear equations in combinatorial Laplacians of 2-complexes up to high accuracy in time Õ((# of nonzero coefficients)^c), then we can solve general linear equations with polynomially bounded integer coefficients and condition numbers up to high accuracy in time Õ((# of nonzero coefficients)^c). We prove this by a nearly-linear time reduction from general linear equations to combinatorial Laplacians of 2-complexes. Our reduction preserves the sparsity of the problem instances up to poly-logarithmic factors.
Cite as

Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, and Peng Zhang. Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 53:1-53:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ding_et_al:LIPIcs.ICALP.2022.53,
  author =	{Ding, Ming and Kyng, Rasmus and Gutenberg, Maximilian Probst and Zhang, Peng},
  title =	{{Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{53:1--53:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.53},
  URN =		{urn:nbn:de:0030-drops-163945},
  doi =		{10.4230/LIPIcs.ICALP.2022.53},
  annote =	{Keywords: Simplicial Complexes, Combinatorial Laplacians, Linear Equations, Fine-Grained Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.64
Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary

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

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Given an unweighted digraph G = (V,E), undergoing a sequence of edge deletions, with m = |E|, n = |V|, we consider the problem of maintaining all-pairs shortest paths (APSP). Whilst this problem has been studied in a long line of research [ACM'81, FOCS'99, FOCS'01, STOC'02, STOC'03, SWAT'04, STOC'13] and the problem of (1+ε)-approximate, weighted APSP was solved to near-optimal update time Õ(mn) by Bernstein [STOC'13], the problem has mainly been studied in the context of an oblivious adversary which fixes the update sequence before the algorithm is started. In this paper, we make significant progress on the problem for an adaptive adversary which can perform updates based on answers to previous queries: - We first present a deterministic data structure that maintains the exact distances with total update time Õ(n³). - We also present a deterministic data structure that maintains (1+ε)-approximate distance estimates with total update time Õ(√m n²/ε) which for sparse graphs is Õ(n^{2+1/2}/ε). - Finally, we present a randomized (1+ε)-approximate data structure which works against an adaptive adversary; its total update time is Õ(m^{2/3}n^{5/3} + n^{8/3}/(m^{1/3}ε²)) which for sparse graphs is Õ(n^{2+1/3}/ε²). Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. [STOC'02] and maintains the distance matrix in near-optimal time. Our approximate data structures improve upon the best data structures against an adaptive adversary which have Õ(mn²) total update time [JACM'81, STOC'03].
Cite as

Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 64:1-64:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{evald_et_al:LIPIcs.ICALP.2021.64,
  author =	{Evald, Jacob and Fredslund-Hansen, Viktor and Gutenberg, Maximilian Probst and Wulff-Nilsen, Christian},
  title =	{{Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{64:1--64:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.64},
  URN =		{urn:nbn:de:0030-drops-141337},
  doi =		{10.4230/LIPIcs.ICALP.2021.64},
  annote =	{Keywords: Dynamic Graph Algorithm, Data Structure, Shortest Paths}
}
  • Refine by Author
  • 2 Gutenberg, Maximilian Probst
  • 2 Kyng, Rasmus
  • 1 Bernstein, Aaron
  • 1 Ding, Ming
  • 1 Evald, Jacob
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Dynamic graph algorithms
  • 1 Mathematics of computing → Algebraic topology
  • 1 Mathematics of computing → Computations on matrices
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Network flows
  • Show More...

  • Refine by Keyword
  • 1 Combinatorial Laplacians
  • 1 Convex optimization
  • 1 Data Structure
  • 1 Data structures
  • 1 Dynamic Graph Algorithm
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2022
  • 1 2021
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact