Bernhard Haeupler

Last Name

Haeupler

First Name

Bernhard

ORCID

0000-0003-3381-0459

Organisational unit

09622 - Steurer, David / Steurer, David

Show all metadata

Search Results

Publications1 - 10 of 46

Low-Congestion shortcuts without embedding
Haeupler, Bernhard; Izumi, Taisuke; Zuzic, Goran (2021)
Distributed Computing
Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. This phenomenon can be seen as the broad underlying reason for the pervasive Ω~(√n+D) lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, [Ghaffari and Hauepler; SODA’16] introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast O(DlogO(1)n) distributed algorithms for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner. Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA’16] relies heavily on having access to a genus embedding of the network. Computing such an embedding distributedly, however, is a hard problem—even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight. In this work, we side-step this problem by defining tree-restricted shortcuts: a more structured and restricted form of shortcuts. We give a novel construction algorithm which efficiently finds such shortcuts that are, up to a logarithmic factor, as good as the best restricted shortcuts that exist for a given network. This new construction algorithm directly leads to an O(DlogO(1)n)-round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist—without the need to compute any embedding. This greatly simplifies the existing planar algorithms and includes the first efficient algorithm for bounded genus graphs.
Network Coding Gaps for Completion Times of Multiple Unicasts
Haeupler, Bernhard; Wajc, David; Zuzic, Goran (2020)
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of k unicasts, proving this gap is at most polylogarithmic in k. Complementing this result, we show there exist instances of k unicasts for which this coding gap is polylogarithmic in k. Our results also hold for average completion time, and more generally any lp norm of completion times.
Reducing Shortcut and Hopset Constructions to Shallow Graphs
Haeupler, Bernhard; Jiang, Yonggang; Saranurak, Thatchaphol (2026)
We introduce a blackbox framework that simplifies all known parallel algorithms with near-linear work for single-source reachability and shortest paths in directed graphs. Specifically, existing reachability algorithms rely on constructing shortcuts; our blackbox allows these algorithms that construct shortcuts with hopbound $h$ to assume the input graph $G$ is ``shallow'', meaning if vertex $s$ can reach vertex $t$, it can do so in approximately $h$ hops. This assumption significantly simplifies shortcut construction [Fin18, JLS19], resulting in simpler parallel reachability algorithms. Furthermore, our blackbox extends naturally to simplify parallel algorithms for constructing hopsets and, consequently, for computing shortest paths [CFR20 , CF23 , RHM+23 ].
Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps
Haeupler, Bernhard; Hladík, Richard; Rozhoň, Václav; et al. (2024)
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure. Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology. We give the first application of this notion to any sequential algorithm. We design a new heap data structure with a working-set property guaranteeing that the heap takes advantage of locality in heap operations. Our heap matches the optimal (worst-case) bounds of Fibonacci heaps but also provides the beyond-worst-case guarantee that the cost of extracting the minimum element is merely logarithmic in the number of elements inserted after it instead of logarithmic in the number of all elements in the heap. This makes the extraction of recently added elements cheaper. We prove that our working-set property guarantees universal optimality for the problem of ordering vertices by their distance from the source vertex: The sequence of heap operations generated by any run of Dijkstra's algorithm on a fixed graph possesses enough locality that one can couple the number of comparisons performed by any heap with our working-set bound to the minimum number of comparisons required to solve the distance ordering problem on this graph for a worst-case choice of arc lengths.
Universally-optimal distributed algorithms for known topologies
Haeupler, Bernhard; Wajc, David; Zuzic, Goran (2021)
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions: (i) What network topology parameters determine the complexity of distributed optimization? (ii) Are there universally-optimal algorithms that are as fast as possible on every topology? We resolve these 25-year-old open problems in the known-topology setting (i.e., supported CONGEST) for a wide class of global network optimization problems including MST, (1+?)-min cut, various approximate shortest paths problems, sub-graph connectivity, etc. In particular, we provide several (equivalent) graph parameters and show they are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. Our results also imply that algorithms based on the low-congestion shortcut framework match the above lower bound, making them universally optimal if shortcuts are efficiently approximable.
Bidirectional Dijkstra’s Algorithm is Instance-Optimal
Haeupler, Bernhard; Hladík, Richard; Rozhoň, Václav; et al. (2025)
Proceedings of the 2025 Symposium on Simplicity in Algorithms (SOSA)
While Dijkstra’s algorithm has near-optimal time complexity for the problem of finding the shortest st-path, in practice, other algorithms are often superior on huge graphs. A prominent such example is the bidirectional search, which executes Dijkstra’s algorithm from both endpoints in parallel and stops when these executions meet. In this paper, we give a strong theoretical justification for the use of such bidirectional search algorithms. We prove that for weighted multigraphs, both directed and undirected, a careful implementation of bidirectional search is instance-optimal with respect to the number of edges it explores. That is, we prove that no correct algorithm can outperform our implementation of bidirectional search on any single instance by more than a constant factor. For unweighted graphs, we show that bidirectional search is instace-optimal up to a factor of O(Δ) where Δ is the maximum degree of the graph. We also show that this is the best possible.
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
Ghaffari, Mohsen; Grunau, Christoph; Haeupler, Bernhard; et al. (2023)
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitting sets, and spanners. As the main ingredient in these results, we develop novel randomized distributed algorithms that we can analyze using only pairwise independence, and we can thus derandomize efficiently. As our most prominent end-result, we obtain a deterministic construction for O(log n)-color O(log n · log log log n)- strong diameter network decomposition in Õ(log3 n) rounds. This is the first construction that achieves almost log n in both parameters, and it improves on a recent line of exciting progress on deterministic distributed network decompositions [Rozhoň, Ghaffari STOC'20; Ghaffari, Grunau, Rozhoň SODA'21; Chang, Ghaffari PODC'21; Elkin, Haeupler, Rozhoň, Grunau FOCS'22].
Synchronization Strings and Codes for Insertions and Deletions - A Survey
Haeupler, Bernhard; Shahrasbi, Amirbehshad (2021)
IEEE Transactions on Information Theory
Already in the 1960s, Levenshtein and others studied error-correcting codes that protect against synchronization errors, such as symbol insertions and deletions. However, despite significant efforts, progress on designing such codes has been lagging until recently, particularly compared to the detailed understanding of error-correcting codes for symbol substitution or erasure errors. This paper surveys the recent progress in designing efficient error-correcting codes over finite alphabets that can correct a constant fraction of worst-case insertions and deletions. Most state-of-the-art results for such codes rely on synchronization strings, simple yet powerful pseudo-random objects that have proven to be very effective solutions for coping with synchronization errors in various settings. This survey also includes an overview of what is known about synchronization strings and discusses communication settings related to error-correcting codes in which synchronization strings have been applied.
Dynamic Deterministic Constant-Approximate Distance Oracles with nϵ Worst-Case Update Time
Haeupler, Bernhard; Long, Yaowei; Saranurak, Thatchaphol (2024)
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph G = (V, E) with n vertices undergoing both edge insertions and deletions, and an arbitrary parameter ϵ∈[1/logcn,1 where c > 0 is a small constant, we can deterministically maintain a data structure with O(nϵ) worst-case update time that, given any pair of vertices (u, v), returns a 2poly(1/ϵ) -approximate distance between u and v in poly(1/E) log log n query time. Our algorithm significantly advances the state-of-the-art in two aspects, both for fully dynamic algorithms and even decremental algorithms. First, no existing algorithm with worst-case update time guarantees a o( n )-approximation while also achieving an n2-Ω(1)update and no(1) query time, while our algorithm offers a constant Oϵ(1) -approximation with O(nϵ) update time and oϵ (log log n) query time. Second, even if amortized update time is allowed, it is the first deterministic constant-approximation algorithm with n1−Ω(1) update and query time. The best result in this direction is the recent deterministic distance oracle by Chuzhoy and Zhang [STOC 2023] which achieves an approxi- mation of (log log n)2O(1/ϵ3) with amortized update time of O(nϵ) and query time of 2p∘1y(1/ϵ)logn log log n. We obtain the result by dynamizing tools related to length- constrained expanders [Haeupler-Racke-Ghaffari, STOC 2022; Haeupler-Hershkowitz-Tan, FOCS 2024]. Our technique com- pletely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Anagnostides, Ioannis; Lenzen, Christoph; Haeupler, Bernhard; et al. (2022)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 36th International Symposium on Distributed Computing (DISC 2022)
In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after no(1)SQ(G) log(1/ε) rounds, where ε is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires (Equation presented)(SQ(G)) rounds, even for a crude solution with ε ≤ 1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D · no(1) log(1/ε) rounds, where D is the hop-diameter of the network; as well as no(1) log(1/ε)-round algorithms for the case of SQ(G) ≤ no(1), which holds for most networks of interest. Conditioned on improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the Supported-CONGEST ones. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity no(1) log(1/ε). The unifying thread of these results, and our main technical contribution, is the study of a novel ρ-congested generalization of the standard part-wise aggregation problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST (with the additional overhead due to standard barriers), as well as a simple algorithm for bounded-treewidth graphs with a quadratic dependence on the congestion ρ. This primitive can be readily used to accelerate the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further independent applications in the future.

Publications1 - 10 of 46

Bernhard Haeupler

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results