research
∙
10/03/2022
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
A singularly (near) optimal distributed algorithm is one that is (near) ...
share
research
∙
04/25/2022
Byzantine-Resilient Counting in Networks
We present two distributed algorithms for the Byzantine counting problem...
research
∙
04/18/2022
Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds
We study the distributed minimum spanning tree (MST) problem, a fundamen...
research
∙
04/18/2022
Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity
Maximal Independent Set (MIS) is one of the central and most well-studie...
research
∙
08/04/2021
Singularly Near Optimal Leader Election in Asynchronous Networks
This paper concerns designing distributed algorithms that are singularly...
research
∙
05/19/2021
Can We Break Symmetry with o(m) Communication?
We study the communication cost (or message complexity) of fundamental d...
research
∙
02/18/2021
Network Size Estimation in Small-World Networks under Byzantine Faults
We study the fundamental problem of counting the number of nodes in a sp...
research
∙
08/06/2020
Singularly Optimal Randomized Leader Election
This paper concerns designing distributed algorithms that are singularly...
research
∙
06/12/2020
Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity
Maximal Independent Set (MIS) is one of the fundamental problems in dist...
research
∙
05/15/2020
Efficient Distributed Algorithms for the K-Nearest Neighbors Problem
The K-nearest neighbors is a basic problem in machine learning with nume...
research
∙
11/06/2019
Distributed MST: A Smoothed Analysis
We study smoothed analysis of distributed graph algorithms, focusing on ...
research
∙
04/16/2019
Efficient Distributed Community Detection in the Stochastic Block Model
Designing effective algorithms for community detection is an important a...
research
∙
10/08/2018
Time-Message Trade-Offs in Distributed Algorithms
This paper focuses on showing time-message trade-offs in distributed alg...
research
∙
09/02/2018
The Complexity of Leader Election: A Chasm at Diameter Two
This paper focuses on studying the message complexity of implicit leader...
research
∙
06/26/2018
The Communication Cost of Information Spreading in Dynamic Networks
This paper investigates the message complexity of distributed informatio...
research
∙
04/24/2018
Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs
We present fast and efficient randomized distributed algorithms to find ...
research
∙
01/05/2018