92 citations · 220 across the 35 of their papers we have counts for
6 papers · 1 filter
Fast Partial Distance Estimation and Applications
Christoph Lenzen, Boaz Patt-Shamir
We study approximate distributed solutions to the weighted {\it all-pairs-shortest-paths} (APSP) problem in the CONGEST model. We obtain the following results. A deterministic…
Algebrisation in Distributed Graph Algorithms: Fast Matrix Multiplication in the Congested Clique
Petteri Kaski, Janne H. Korhonen, Christoph Lenzen +1
While algebrisation constitutes a powerful technique in the design and analysis of centralised algorithms, to date there have been hardly any applications of algebraic techniques i…
The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm
Pierre Bertrand, Christoph Lenzen
In this work, we examine a generic class of simple distributed balls-into-bins algorithms. Exploiting the strong concentration bounds that apply to balls-into-bins games, we provid…
Improved Distributed Steiner Forest Construction
Christoph Lenzen, Boaz Patt-Shamir
We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant , a -approximati…
Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication
Christoph Lenzen, Nancy Lynch, Calvin Newport +1
We consider the ANTS problem [Feinerman et al.] in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the b…
Local Approximability of Minimum Dominating Set on Planar Graphs
Miikka Hilke, Christoph Lenzen, Jukka Suomela
We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a -approximation of a minimum dominating set on planar graphs,…