92 citations · 220 across the 35 of their papers we have counts for
5 papers · 1 filter
Small Hazard-free Transducers
Johannes Bund, Christoph Lenzen, Moti Medina
Ikenmeyer et al. (JACM'19) proved an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions. This raises th…
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion
Amir Abboud, Keren Censor-Hillel, Seri Khoury +1
We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of \emph{fooling views} and exemplify its strength by…
A Local Algorithm for the Sparse Spanning Graph Problem
Christoph Lenzen, Reut Levi
Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide…
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Sebastian Forster, Andreas Karrenbauer +1
We present a method for solving the transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of in undirected graphs w…
Near-Optimal Distributed Maximum Flow
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn +2
We present a near-optimal distributed algorithm for -approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(…