5 citations · 12 across the 9 of their papers we have counts for
9 papers
Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
Christoph Lenzen, Sophie Wenning
A long-standing open question is which graph class is the most general one permitting constant-time constant-factor approximations for dominating sets. The approximation ratio has…
On Specifications and Proofs of Timed Circuits
Matthias Fuegger, Christoph Lenzen, Ulrich Schmid
Given a discrete-state continuous-time reactive system, like a digital circuit, the classical approach is to first model it as a state transition system and then prove its properti…
Near-Optimal Self-Stabilising Counting and Firing Squads
Christoph Lenzen, Joel Rybicki
Consider a fully-connected synchronous distributed system consisting of nodes, where up to nodes may be faulty and every node starts in an arbitrary initial state. In the s…
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…