Bernhard Haeupler

Bernhard Haeupler, Anton Paramonov

We study and further develop powerful general-purpose schemes to maintain random assignments under adversarial dynamic changes. The goal is to maintain assignments that are (approximately) distributed similarly as a completely fresh resampling of all assignments after each change, while doing only a few resamples per change. This becomes particularly interesting and challenging when dynamics are controlled by an adaptive adversary. Our work builds on and further develops the proactive resampling technique [Bhattacharya, Saranurak, and Sukprasert ESA'22]. We identify a new ``temporal selection'' attack that adaptive adversaries can use to cause biases, even against proactive resampling. We propose a new ''temporal aggregation'' principle that algorithms should follow to counteract these biases, and present two powerful new resampling schemes based on this principle. We give various applications of our new methods. The main one in maintaining proper coloring of the graph under adaptive adversarial modifications: we maintain $O(Δ)$ coloring for general graphs with maximum degree $Δ$ and $O(\fracΔ{\ln Δ})$ coloring for triangle free graphs, both with sublinear in the number of vertices average work per modification. Other applications include efficiently maintaining random walks in dynamically changing graphs.

Bernhard Haeupler, Richard Hladík, John Iacono et al.

We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $O(\log T)$ on the number of comparisons has a time bound of $O(n^{2.5})$ and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-$k$ sorting problem: Given $k$ and the outcomes of some pre-existing comparisons, output the smallest $k$ items in sorted order. The modified algorithm solves the top-$k$ sorting problem in minimum time and comparisons, to within constant factors.

Bernhard Haeupler, Yaowei Long, Antti Roeyskoe et al.

A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph $G$ with $n$ vertices so that, for any edge set $F$ of size $|F| \leq f$, one can approximate the distance between $p$ and $q$ in $G \setminus F$ by reading only the labels of $F \cup \{p,q\}$. For any $k$, we present a deterministic polynomial-time scheme with $O(k^{4})$ approximation and $\tilde{O}(f^{4}n^{1/k})$ label size. This is the first scheme to achieve a constant approximation while handling any number of edge faults $f$, resolving the open problem posed by Dory and Parter [DP21]. All previous schemes provided only a linear-in-$f$ approximation [DP21, LPS25]. Our labeling scheme directly improves the state of the art in the simpler setting of distance sensitivity oracles. Even for just $f = Θ(\log n)$ faults, all previous oracles either have super-linear query time, linear-in-$f$ approximation [CLPR12], or exponentially worse $2^{{\rm poly}(k)}$ approximation dependency in $k$ [HLS24].

Bernhard Haeupler, Antti Roeyskoe, Zhijun Zhang

All parallel algorithms for directed reachability and shortest paths crucially rely on efficient shortcut constructions. These constructions find directed paths and shortcut them by adding edges, with the goal to reduce the diameter of the graph. A long sequence of works has studied (efficient) shortcut constructions as well as impossibility results on the best diameter and therefore the best parallelism that can be achieved via this approach. This paper introduces a new conceptual tool for this line of research in the form of a simple and natural structural criterion: A shortcut $H$ for a graph $G$ is certified if for any shortcut edge $(u, v) \in H$, there exists a vertex $w$ such that the edges $(u, w)$ and $(w, v)$ are also in $G \cup H$. We show that this criterion captures constructiveness in the following sense: A shortcut $H$ can be constructed in $t$ time by repeatedly spending $\ell$ time on shortcutting a path of length $\ell$, if and only if, there exists a certified shortcut $H' \supseteq H$ of size $\tilde{O}(t)$. Furthermore, all known shortcut constructions with efficient algorithms can be extended to produce certified shortcuts of size $\tilde{O}(m)$. On the other hand, for shortcut constructions for which attempts to find efficient implementations have failed, we can show that this is impossible. We also obtain stronger diameter lower bounds for certified shortcuts and hopsets. For example, no certified shortcut construction with almost-linear size can reduce a graph's diameter below $n^{1/4-o(1)}$. This seems to be the best bound one can hope for with current techniques.

Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg et al.

A function $φ:\{0,1\}^n \to \{0,1\}^N$ is called an isometric embedding of the $n$-dimensional Hamming metric space to the $N$-dimensional edit metric space if, for all $x,y\in\{0,1\}^n$, the Hamming distance between $x$ and $y$ is equal to the edit distance between $φ(x)$ and $φ(y)$. The rate of such an embedding is defined as the ratio $n/N$. It is well known in the literature how to construct isometric embeddings with rate $Ω(1/\log n)$. However, achieving even near-isometric embeddings with positive constant rate has remained elusive until now. In this paper, we present an isometric embedding with rate $1/8$ by discovering connections to synchronization strings, which were studied in the context of insertion-deletion codes (Haeupler-Shahrasbi [JACM'21]). At a technical level, we introduce a framework for obtaining high-rate isometric embeddings using a novel object called misaligners. As an immediate consequence of our constant-rate isometric embedding, we improve known conditional lower bounds for various optimization problems in the edit metric, now with optimal dependence on the dimension. We complement our results by showing that no isometric embedding $φ:\{0,1\}^n \to \{0,1\}^N$ can have rate greater than $15/32$ for all positive integers $n$. En route to proving this upper bound, we uncover fundamental structural properties necessary for every Hamming-to-edit isometric embedding. We also prove similar upper and lower bounds for embeddings over larger alphabets. Finally, we consider embeddings $φ:Σ_{\mathrm{in}}^n \to Σ_{\mathrm{out}}^N$ between different input and output alphabets, where the rate is given by $\frac{n\log|Σ_{\mathrm{in}}|}{N\log|Σ_{\mathrm{out}}|}$. In this setting, we show that the rate can be made arbitrarily close to $1$.

Diptarka Chakraborty, Hendrik Fichtenberger, Bernhard Haeupler et al.

Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge attracting growing attention. Traditional approaches focus on the stability of cluster centers; unfortunately, this neglects the real-world need for stable point labels, i.e., stable assignments of points to named sets (clusters). In this paper, we address this gap by initiating the study of label-consistent metric clustering. We first introduce a new notion of consistency, measuring the label distance between two consecutive solutions. Then, armed with this new definition, we design new consistent approximation algorithms for the classical $k$-center and $k$-median problems.

Bernhard Haeupler, Richard Hladík, Shengzhe Wang et al.

This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directed graphs, tighten and generalize probabilistic guarantees, and prove new independence results between (far away) edges. Our results are the first to give meaningful guarantees for decompositions with small diameters $D = Ω(\log\log n)$ in contrast to the state of the art that only applies to super-logarithmic diameters $D = ω(\log n)$. These results transfer several important and widely used aspects of undirected low-diameter decompositions to the directed setting. All our results are algorithmic -- small modifications to two existing directed low-diameter decompositions [BFHL25; Li25] can be used to sample decompositions with our new guarantees in near-linear time $\tilde{O}(m)$.

Bernhard Haeupler, Slobodan Mitrović, Srikkanth Ramachandran et al.

This paper proves that a wide class of local search algorithms extend as is to the fully dynamic setting with an adaptive adversary, achieving an amortized $\tilde{O}(1)$ number of local-search steps per update. A breakthrough by Moser (2009) introduced the witness-tree and entropy compression techniques for analyzing local resampling processes for the Lovász Local Lemma. These methods have since been generalized and expanded to analyze a wide variety of local search algorithms that can efficiently find solutions to many important local constraint satisfaction problems. These algorithms either extend a partial valid assignment and backtrack by unassigning variables when constraints become violated, or they iteratively fix violated constraints by resampling their variables. These local resampling or backtracking procedures are incredibly flexible, practical, and simple to specify and implement. Yet, they can be shown to be extremely efficient on static instances, typically performing only (sub)-linear number of fixing steps. The main technical challenge lies in proving conditions that guarantee such rapid convergence. This paper extends these convergence results to fully dynamic settings, where an adaptive adversary may add or remove constraints. We prove that applying the same simple local search procedures to fix old or newly introduced violations leads to a total number of resampling steps near-linear in the number of adversarial updates. Our result is very general and yields several immediate corollaries. For example, letting $Δ$ denote the maximum degree, for a constant $ε$ and $Δ= \text{poly}(\log n)$, we can maintain a $(1+ε) Δ$-edge coloring in $\text{poly}(\log n)$ amortized update time against an adaptive adversary. The prior work for this regime has exponential running time in $\sqrt{\log n}$ [Christiansen, SODA '26].

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

We show that every directed graph $G$ with $n$ vertices and $m$ edges admits a directed acyclic graph (DAG) with $m^{1+o(1)}$ edges, called a DAG projection, that can either $(1+1/\text{polylog} (n))$-approximate distances between all pairs of vertices $(s,t)$ in $G$, or $n^{o(1)}$-approximate maximum flow between all pairs of vertex subsets $(S,T)$ in $G$. Previous similar results suffer a $Ω(\log n)$ approximation factor for distances [Assadi, Hoppenworth, Wein, STOC'25] [Filtser, SODA'26] and, for maximum flow, no prior result of this type is known. Our DAG projections admit $m^{1+o(1)}$-time constructions. Further, they admit almost-optimal parallel constructions, i.e., algorithms with $m^{1+o(1)}$ work and $m^{o(1)}$ depth, assuming the ones for approximate shortest path or maximum flow on DAGs, even when the input $G$ is not a DAG. DAG projections immediately transfer results on DAGs, usually simpler and more efficient, to directed graphs. As examples, we improve the state-of-the-art of $(1+ε)$-approximate distance preservers [Hoppenworth, Xu, Xu, SODA'25] and single-source minimum cut [Cheung, Lau, Leung, SICOMP'13], and obtain simpler construction of $(n^{1/3},ε)$-hop-set [Kogan, Parter, SODA'22] [Bernstein, Wein, SODA'23] and combinatorial max flow algorithms [Bernstein, Blikstad, Saranurak, Tu, FOCS'24] [Bernstein, Blikstad, Li, Saranurak, Tu, FOCS'25]. Finally, via DAG projections, we reduce major open problems on almost-optimal parallel algorithms for exact single-source shortest paths (SSSP) and maximum flow to easier settings: (1) From exact directed SSSP to exact undirected ones, (2) From exact directed SSSP to $(1+1/\text{polylog}(n))$-approximation on DAGs, and (3) From exact directed maximum flow to $n^{o(1)}$-approximation on DAGs.