Simon Meierhans
YOU?
Author Swipe
View article: Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time Open
Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions $e_1, e_2, \ldots, e_k$ to an $m$-edge graph $G$ that is initially a $ϕ$-expander, the algorithm can grow a set $P \…
View article: Bootstrapping Dynamic APSP via Sparsification
Bootstrapping Dynamic APSP via Sparsification Open
We give a simple algorithm for the dynamic approximate All-Pairs Shortest Paths (APSP) problem. Given a graph G = (V, E, l) with polynomially bounded edge lengths, our data structure processes |E| edge insertions and deletions in total tim…
View article: Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal Open
Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $ϕ$-expander decomposition is a partition $V_1, V_2, \ldots, V_k$ of the vertex set $V$ w…
View article: A Simple Dynamic Spanner via APSP
A Simple Dynamic Spanner via APSP Open
We give a simple algorithm for maintaining a $n^{o(1)}$-approximate spanner $H$ of a graph $G$ with $n$ vertices as $G$ receives edge updates by reduction to the dynamic All-Pairs Shortest Paths (APSP) problem. Given an initially empty gra…
View article: Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality Open
We give the first almost-linear total time algorithm for deciding if a flow of cost at most $F$ still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, and…
View article: Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow Open
We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, s-t shortest path, maximum flow, and minimum-cost flow. To solve these problems…
View article: A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications Open
We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in graphs undergoing edge insertions and/or deletions. In particular, we obtain the following results:
View article: Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, $s$-$t$ Shortest Path, and Minimum-Cost Flow
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, $s$-$t$ Shortest Path, and Minimum-Cost Flow Open
We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, $s$-$t$ shortest path, maximum flow, and minimum-cost flow. To solve these prob…
View article: A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications Open
We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs. In an $m$-edge graph undergoing edge insertions and deletions, our data structures give the first al…
View article: Derandomizing Directed Random Walks in Almost-Linear Time
Derandomizing Directed Random Walks in Almost-Linear Time Open
In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions imply the first deterministic almost-linear time algorithms…
View article: Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier Open
Given a directed, weighted graph $G=(V,E)$ undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances from a dedicated source $s$ while optimizing the total tim…
View article: Content Adaptive Optimization for Neural Image Compression
Content Adaptive Optimization for Neural Image Compression Open
The field of neural image compression has witnessed exciting progress as recently proposed architectures already surpass the established transform coding based approaches. While, so far, research has mainly focused on architecture and mode…
View article: Resilient Dictionaries for Randomly Unreliable Memory
Resilient Dictionaries for Randomly Unreliable Memory Open
We study the problem of designing a dictionary data structure that is resilient to memory corruptions. Our error model is a variation of the faulty RAM model in which, except for constant amount of definitely reliable memory, each memory w…
View article: Transformations of High-Level Synthesis Codes for High-Performance Computing
Transformations of High-Level Synthesis Codes for High-Performance Computing Open
Spatial computing architectures promise a major stride in performance and energy efficiency over the traditional load/store devices currently employed in large scale computing systems. The adoption of high-level synthesis (HLS) from langua…