Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
From MaRDI portal
Publication:6071121
DOI10.1007/s00446-023-00454-0arXiv2109.05151MaRDI QIDQ6071121
Christoph Lenzen, Bernhard Haeupler, Ioannis Anagnostides, Themis Gouleakis, Goran Zuzic
Publication date: 21 November 2023
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.05151
Related Items (max. 100)
Cites Work
- Unnamed Item
- Unnamed Item
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Simple distributed \(\Delta+1\)-coloring of graphs
- Near-optimal low-congestion shortcuts on bounded parameter graphs
- Near-Optimal Scheduling of Distributed Algorithms
- Near-Optimal Distributed Maximum Flow
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- On the power of the congested clique model
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- Locality in Distributed Graph Algorithms
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
- Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
- Shortest Paths in a Hybrid Network Model
- Fully dynamic spectral vertex sparsifiers and applications
- An efficient parallel solver for SDD linear systems
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Sparsified Cholesky and multigrid solvers for connection laplacians
- Low-Congestion Shortcuts without Embedding
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Lx = b
- Approaching Optimality for Solving SDD Linear Systems
- Distributed verification and hardness of distributed approximation
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Computing Shortest Paths and Diameter in the Hybrid Network Model
- Universally-optimal distributed algorithms for known topologies
- Time-optimal construction of overlay networks
This page was built for publication: Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
