46 citations · 313 across the 68 of their papers we have counts for
6 papers · 1 filter
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast
Bernhard Haeupler, D Ellis Hershkowitz, Thatchaphol Saranurak
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as -length flows…
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
Goran Zuzic, Gramoz Goranci, Mingquan Ye +2
We provide universally-optimal distributed graph algorithms for -approximate shortest path problems including shortest-path-tree and transshipment. The universal o…
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler +2
In this paper, we refine the (almost) \emph{existentially optimal} distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (a…
Universally-Optimal Distributed Algorithms for Known Topologies
Bernhard Haeupler, David Wajc, Goran Zuzic
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do b…
Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic
Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorith…
Synchronization Strings and Codes for Insertions and Deletions -- a Survey
Bernhard Haeupler, Amirbehshad Shahrasbi
Already in the 1960s, Levenshtein and others studied error-correcting codes that protect against synchronization errors, such as symbol insertions and deletions. However, despite s…