research
∙
08/08/2023
One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks
The paper compares two generic techniques for deriving lower bounds and ...
share
research
∙
07/26/2023
Distributed Certification for Classes of Dense Graphs
A proof-labeling scheme (PLS) for a boolean predicate Π on labeled graph...
research
∙
06/02/2023
Parameterized Complexity of Broadcasting in Graphs
The task of the broadcast problem is, given a graph G and a source verte...
research
∙
04/05/2023
On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST Model
It is known that, for every k≥ 2, C_2k-freeness can be decided by a gene...
research
∙
01/27/2023
Energy-Efficient Distributed Algorithms for Synchronous Networks
We study the design of energy-efficient algorithms for the LOCAL and CON...
research
∙
08/04/2022
Computing Power of Hybrid Models in Synchronous Networks
During the last two decades, a small set of distributed computing models...
research
∙
07/22/2022
Fault Tolerant Coloring of the Asynchronous Cycle
We present a wait-free algorithm for proper coloring the n nodes of the ...
research
∙
06/10/2022
A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement
We study two fundamental problems of distributed computing, consensus an...
research
∙
12/06/2021
A Meta-Theorem for Distributed Certification
Distributed certification, whether it be proof-labeling schemes, locally...
research
∙
08/04/2021
On Extending Brandt's Speedup Theorem from LOCAL to Round-Based Full-Information Models
Given any task Π, Brandt's speedup theorem (PODC 2019) provides a mechan...
research
∙
05/25/2021
The Topology of Randomized Symmetry-Breaking Distributed Computing
Studying distributed computing through the lens of algebraic topology ha...
research
∙
12/29/2020
Present-Biased Optimization
This paper explores the behavior of present-biased agents, that is, agen...
research
∙
07/16/2020
Local Certification of Graphs with Bounded Genus
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for aut...
research
∙
05/12/2020
Compact Distributed Certification of Planar Graphs
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the exist...
research
∙
03/06/2020
The Topology of Local Computing in Networks
Modeling distributed computing in a way enabling the use of formal metho...
research
∙
02/24/2020
Distributed Quantum Proofs for Replicated Data
The paper tackles the issue of checking that all copies of a large data ...
research
∙
01/22/2020
Simple and Fast Distributed Computation of Betweenness Centrality
Betweenness centrality is a graph parameter that has been successfully a...
research
∙
08/09/2019
Trade-offs in Distributed Interactive Proofs
The study of interactive proofs in the context of distributed network co...
research
∙
07/08/2019
A Topological Perspective on Distributed Network Algorithms
More than two decades ago, combinatorial topology was shown to be useful...
research
∙
04/16/2019
Distributed Computing in the Asynchronous LOCAL model
The LOCAL model is among the main models for studying locality in the fr...
research
∙
03/08/2018