92 citations · 220 across the 35 of their papers we have counts for
5 papers · 1 filter
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…
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen +3
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows th…
Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Christoph Lenzen, Joel Rybicki
We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the nodes has its own clock. Our algorithms operate in a very strong fault…
Robust Routing Made Easy
Christoph Lenzen, Moti Medina, Mehrdad Saberi +1
With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important…
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…