research
∙
05/19/2023
Distributed MIS with Low Energy and Time Complexities
We present randomized distributed algorithms for the maximal independent...
share
research
∙
05/10/2023
A Near-Optimal Deterministic Distributed Synchronizer
We provide the first deterministic distributed synchronizer with near-op...
research
∙
05/10/2023
Average Awake Complexity of MIS and Matching
Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the no...
research
∙
04/19/2023
Coloring Fast with Broadcasts
We present an O(log^3log n)-round distributed algorithm for the (Δ+1)-co...
research
∙
04/19/2023
Nearly Work-Efficient Parallel DFS in Undirected Graphs
We present the first parallel depth-first search algorithm for undirecte...
research
∙
03/28/2023
Faster Deterministic Distributed MIS and Approximate Matching
We present an Õ(log^2 n) round deterministic distributed algorithm for t...
research
∙
01/16/2023
A Distributed Palette Sparsification Theorem
Is fully decentralized graph streaming possible? We consider this questi...
research
∙
11/21/2022
A Cut-Matching Game for Constant-Hop Expanders
This paper provides a cut-strategy that produces constant-hop expanders ...
research
∙
11/14/2022
Massively Parallel Algorithms for b-Matching
This paper presents an O(loglogd̅) round massively parallel algorithm fo...
research
∙
11/09/2022
A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph
The minimum-cost k-edge-connected spanning subgraph (k-ECSS) problem is ...
research
∙
10/03/2022
Local Computation of Maximal Independent Set
We present a randomized Local Computation Algorithm (LCA) with query com...
research
∙
09/23/2022
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
This paper presents significantly improved deterministic algorithms for ...
research
∙
09/23/2022
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
We develop a general deterministic distributed method for locally roundi...
research
∙
08/17/2022
Node and Edge Averaged Complexities of Local Graph Problems
The node-averaged complexity of a distributed algorithm running on a gra...
research
∙
06/10/2022
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
We describe a simple deterministic O( ε^-1logΔ) round distributed algori...
research
∙
05/30/2022
Universally-Optimal Distributed Exact Min-Cut
We present a universally-optimal distributed algorithm for the exact wei...
research
∙
04/29/2022
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
This paper presents efficient distributed algorithms for a number of fun...
research
∙
02/19/2021
Strong-Diameter Network Decomposition
Network decomposition is a central concept in the study of distributed g...
research
∙
11/20/2020
Hop-Constrained Oblivious Routing
We prove the existence of an oblivious routing scheme that is poly(log n...
research
∙
11/09/2020
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
We present a simple deterministic distributed algorithm that computes a ...
research
∙
08/07/2020
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
We prove that any n-node graph G with diameter D admits shortcuts with c...
research
∙
07/16/2020
Improved Deterministic Network Decomposition
Network decomposition is a central tool in distributed graph algorithms....
research
∙
05/21/2020
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
We present a massively parallel algorithm, with near-linear memory per m...
research
∙
03/02/2020
Massively Parallel Algorithms for Distance Approximation and Spanners
Over the past decade, there has been increasing interest in distributed/...
research
∙
02/22/2020
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
We present O(loglog n) round scalable Massively Parallel Computation alg...
research
∙
09/02/2019
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
We provide a simple new randomized contraction approach to the global mi...
research
∙
08/09/2019
Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond
Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and P...
research
∙
07/25/2019
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
We present a simple polylogarithmic-time deterministic distributed algor...
research
∙
06/02/2019
On the Use of Randomness in Local Distributed Graph Algorithms
We attempt to better understand randomization in local distributed graph...
research
∙
05/28/2019
On the Complexity of Distributed Splitting Problems
One of the fundamental open problems in the area of distributed graph al...
research
∙
05/26/2019
Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
The minimum-weight 2-edge-connected spanning subgraph (2-ECSS) problem i...
research
∙
08/25/2018
Simple Graph Coloring Algorithms for Congested Clique and Massively Parallel Computation
We present a very simple randomized partitioning procedure for graph col...
research
∙
07/17/2018
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
We introduce a method for sparsifying distributed algorithms and exhibit...
research
∙
05/18/2018
Distributed Computation in the Node-Congested Clique
The Congested Clique model of distributed computing, which was introduce...
research
∙
05/12/2018
New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
We show that many classical optimization problems --- such as (1±ϵ)-appr...
research
∙
03/08/2018
Improved Distributed Δ-Coloring
We present a randomized distributed algorithm that computes a Δ-coloring...
research
∙
02/22/2018
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
We present O( n)-round algorithms in the Massively Parallel Computation ...
research
∙
02/19/2018
A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
Sampling constitutes an important tool in a variety of areas: from machi...
research
∙
12/25/2017
Improved Distributed Algorithms for Exact Shortest Paths
Computing shortest paths is one of the central problems in the theory of...
research
∙
11/15/2017
Deterministic Distributed Edge-Coloring with Fewer Colors
We present a deterministic distributed algorithm, in the LOCAL model, th...
research
∙
11/06/2017